71. 简化路径 Medium

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

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

• 一个点 '.' 表示当前目录本身。

• 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。

• 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。

• 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

• 返回的 简化路径 必须遵循下述格式：

• 始终以斜杠 '/' 开头。

• 两个目录名之间必须只有一个斜杠 '/' 。

• 最后一个目录名（如果存在）不能 以 '/' 结尾。

• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

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

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

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

示例 3：
输入：path = "/home/user/Documents/../Pictures"
输出："/home/user/Pictures"
解释：两个点 ".." 表示上一级目录（父目录）。

示例 4：
输入：path = "/../"
输出："/"
解释：不可能从根目录上升一级目录。

示例 5：
输入：path = "/.../a/../b/c/../d/./"
输出："/.../b/d"
解释："..." 在这个问题中是一个合法的目录名。

解题思路

输入：一个字符串 path输出：返回更加简洁的规范路径

本题属于 基础栈 问题。

• 我们可以按 / 分割路径片段，逐个处理：
• 遇到 "" 或 "."：跳过（当前目录）。
• 遇到 ".."：弹栈（返回上一级，若栈空则无操作）。
• 其他正常目录名：入栈。
• 最终用 '/' + '/'.join(stack) 拼成规范绝对路径。

代码实现

python

class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for part in path.split('/'):
            if part == "" or part == ".":   # 空片段或当前目录，忽略
                continue
            if part == "..":                # 上一级，弹栈（若有）
                if stack:
                    stack.pop()
            else:                           # 正常目录名，入栈
                stack.append(part)
        # 根目录是 "/"；否则按 "/" 连接
        return "/" + "/".join(stack)

javascript

/**
 * @param {string} path
 * @return {string}
 */
var simplifyPath = function(path) {
    const stack = [];

    path.split('/').forEach(part => {
        if (part === '' || part === '.') return;

        if (part === '..') {
            if (stack.length) stack.pop();
        } else {
            stack.push(part);
        }
    });
    return '/' + stack.join('/');
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

71 国际版

71 中文版