71. 简化路径

题目链接：71. 简化路径

题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。
• 两个目录名之间必须只有一个斜杠 '/' 。
• 最后一个目录名（如果存在）不能以 '/' 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的规范路径。

核心思考：栈的应用

解决这道题可以直观地使用栈（Stack）来模拟目录的进入和退出过程。Unix 路径的规则极为明确，通过对斜杠 / 进行切分后，路径段可以分为四种情况处理：

1. 空字符串 ""：由于原路径中可能存在连续斜杠 // ，切割后会产生空字符串。直接忽略即可。
2. 当前目录 "."：表示留在当前层级，无任何实际目录切换效果。直接忽略。
3. 返回上一级 ".."：表示退回父目录。在栈的操作上，这等价于弹出栈顶元素。如果此时栈已经为空（代表处于根目录），根据 Unix 规则不能再向越界查找上一级，所以不执行弹出操作，直接忽略。
4. 正常目录名：代表进入下一级目录。遇到有效目录名时，直接将其压入栈中。

遍历并处理完毕后，栈内剩余的元素即为到达目标路径所需保留的合法有效目录名。

最后，我们将栈中的目录名称依次用 "/" 拼接。因为需要保证顶层父目录在最前方，您可以如代码中所示采用逆向循环累加的方法（先弹出的一定是底层子目录），拼接成最终能够被识别并定位的合法路径。

解题思路 (Python)

class Solution:
    def simplifyPath(self, path: str) -> str:
        # 给你一组由 / 隔开的字符串（忽略空串和 .），请你从左到右遍历这些字符串，依次删除每个 .. 及其左侧的字符串（模拟返回上一级目录）。
        spilted = path.split("/")

        # 创建一个栈来模拟
        # 因为..比较好弹
        stack = []
        for part in spilted:
            if part == "" or part == ".":
                continue
            if part == "..":
                if stack:
                    stack.pop()
                continue
            stack.append(part)
        
        # 超级拼装 先弹出来的是靠后的
        temp = ""
        while stack:
            temp = "/" + stack.pop() + temp
        if temp:
            return temp
        else:
            return "/"

复杂度分析

• 时间复杂度：$O(N)$，其中 $N$ 是字符串 path 的长度。通过 split("/") 进行字符串切分需要遍历整条路径消耗 $O(N)$，随后的遍历栈内处理操作以及最终字符串的重新拼装均保持在线性级工时。
• 空间复杂度：$O(N)$。在最坏设定下（例如路径极长且全为目录级别向下深入），除了通过 split() 切分分解得到的数组外，维护的堆栈需要原封不动地容纳和承载所有的目录成分，因此额外储存损耗与原始输入字符串数量一致。