0071. 简化路径

ITCharge大约 3 分钟

---

0071. 简化路径

标签：栈、字符串
难度：中等

题目链接

0071. 简化路径 - 力扣

题目大意

描述：

在 Unix 风格的文件系统中规则如下：

一个点 '.' 表示当前目录本身。
此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件 / 目录名称。

给定一个字符串 $path$ ，表示指向某一文件或目录的 Unix 风格绝对路径（以 '/' 开头），

要求：

请你将其转化为更加简洁的规范路径。返回简化后得到的规范路径。

说明：

$1 \le path.length \le 3000$ 。
path 由英文字母，数字，'.'，'/' 或 '_' 组成。
path 是一个有效的 Unix 风格绝对路径。
返回的简化路径必须遵循下述格式：
- 始终以斜杠 '/' 开头。
- 两个目录名之间必须只有一个斜杠 '/'。
- 最后一个目录名（如果存在）不能以 '/' 结尾。
- 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

示例：

示例 1：

输入：path = "/home/"
输出："/home"
解释：应删除尾随斜杠。

示例 2：

输入：path = "/home//foo/"
输出："/home/foo"
解释：多个连续的斜杠被单个斜杠替换。

解题思路

思路 1：栈

核心思想：

使用栈来模拟路径的层级结构，根据不同的路径组件进行相应的栈操作，最后将栈中的元素组合成简化后的路径。

算法步骤：

分割路径：将输入路径 $path$ 按照 '/' 分割成路径组件数组 $components$ 。
遍历组件：遍历每个路径组件 $component$ $co m p o n e n t$ ：
- 如果 $component$ 为空字符串或 '.'，跳过（表示当前目录）。
- 如果 $component$ 为 '..'，弹出栈顶元素（表示返回上一级目录）。
- 否则，将 $component$ 压入栈中（表示进入下一级目录）。
构建结果：将栈中的元素用 '/' 连接，并在前面加上 '/' 作为根目录。

关键点：

使用栈来维护当前路径的层级结构。
遇到 '..' 时弹出栈顶，遇到有效目录名时压入栈中。
最终结果以 '/' 开头，表示绝对路径。

思路 1：代码

class Solution:
    def simplifyPath(self, path: str) -> str:
        """
        简化 Unix 风格的绝对路径
        """
        # 使用栈来存储路径组件
        stack = []
        
        # 按照 '/' 分割路径
        components = path.split('/')
        
        # 遍历每个路径组件
        for component in components:
            if component == '' or component == '.':
                # 空字符串或 '.' 表示当前目录，跳过
                continue
            elif component == '..':
                # '..' 表示返回上一级目录，弹出栈顶元素
                if stack:
                    stack.pop()
            else:
                # 有效的目录名，压入栈中
                stack.append(component)
        
        # 构建简化后的路径
        # 如果栈为空，返回根目录 '/'
        if not stack:
            return '/'
        
        # 将栈中的组件用 '/' 连接，并在前面加上 '/'
        return '/' + '/'.join(stack)

思路 1：复杂度分析

时间复杂度： $O(n)$ ，其中 $n$ 是路径的长度。需要遍历路径一次，每个字符最多被处理一次。
空间复杂度： $O(n)$ ，其中 $n$ 是路径的长度。栈最多存储 $O(n)$ 个路径组件。