简化路径 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

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

Unix 规则简要：

'.' 表示当前目录；'..' 表示上一级（父目录）。
任意多个连续斜杠视为单个 '/'。
'...' 等多点形式是合法目录名，不是 '..'。

返回路径须以 '/' 开头、目录间仅一个斜杠、末尾无多余斜杠，且不含 '.' / '..' 分量。

1 <= path.length <= 3000

示例 1

输入：path = "/home/"

输出："/home"

删除尾随斜杠。

示例 2

输入：path = "/home//foo/"

输出："/home/foo"

连续斜杠合并为一个。

示例 3

输入：path = "/home/user/Documents/../Pictures"

输出："/home/user/Pictures"

.. 回退一级，去掉 Documents。

示例 4

输入：path = "/../"

输出："/"

已在根目录，无法再向上一级。

示例 5

输入：path = "/.../a/../b/c/../d/./"

输出："/.../b/d"

... 是合法目录名，不是 ..。

💭 模拟答题者思考

1. 暴力思路：按规则手写状态机，遇到 .. 就字符串里找上一段目录删掉——要处理尾随斜杠、连续斜杠、根边界，字符串反复切片拼接，又慢又易错。

2. 重复在哪里？每次 .. 都是「撤销最近进入的一层目录」——后进先出，和括号匹配一样，天然是栈。

3. 先把 path 按 '/' 切开，连续斜杠会产生空串，直接跳过；. 表示留在当前层，也跳过；普通名字入栈；.. 则栈非空时弹出栈顶（根目录不能再退）。

4. 手推 /home/user/Documents/../Pictures：栈依次 home → user → Documents，.. 弹出 Documents，再入 Pictures，拼接得 /home/user/Pictures。

5. 最后用 '/' + '/'.join(stk) 输出；栈空表示只有根，返回 '/'。每个字符参与切分与入栈出栈各常数次，总 O(n)。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`stk`	list / stack	定义：从根到当前位置的路径上，各层目录名（不含斜杠）维护：栈底是根下第一层目录，栈顶是当前最深目录更新：遇普通目录名 `push`；遇 `..` 且栈非空则 `pop`；遇 `.` 或空串不操作
`part`	str	定义：按 `'/'` 切分后当前处理的一个路径分量维护：从左到右依次处理每个非空逻辑段（空段来自连续斜杠）更新：每轮循环取下一个 `part`，严格用 `==` 区分 `..` 与 `...`
`parts`	list[str]	定义：`path.split('/')` 得到的片段序列维护：首元素因绝对路径常为 `''`，遍历时跳过空串即可更新：一次性切分，不在此步做 `..` 语义

⌨️ 落码步骤

1. parts = path.split('/')，初始化空栈 stk = []

2. 遍历每个 part：若 part == '' 或 part == '.'，continue

3. 若 part == '..'：若 stk 非空则 stk.pop()（根目录不 pop）

4. 否则（普通目录名，含 ... 等）：stk.append(part)

5. 返回 '/' + '/'.join(stk)（stk 空时即为 '/'）

💻 代码实现

class Solution:
    def simplifyPath(self, path: str) -> str:
        stk: list[str] = []
        for part in path.split('/'):
            if not part or part == '.':
                continue
            if part == '..':
                if stk:
                    stk.pop()
            else:
                stk.append(part)
        return '/' + '/'.join(stk)

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> stk;
        string part;
        stringstream ss(path);
        while (getline(ss, part, '/')) {
            if (part.empty() || part == ".") continue;
            if (part == "..") {
                if (!stk.empty()) stk.pop_back();
            } else {
                stk.push_back(part);
            }
        }
        string res = "/";
        for (size_t i = 0; i < stk.size(); ++i) {
            if (i) res += "/";
            res += stk[i];
        }
        return res.empty() ? "/" : res;
    }
};
// 时间 O(n)，空间 O(n)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(n)

⚠️ 常见坑

❗ 把 ... 当成 ..：必须用 part == ".." 精确匹配，不能用前缀或点数判断。

❗ 根目录再 ..：栈已空时不能再 pop，结果应仍为 /，不能变成空串。

❗ 拼接结果多写尾随斜杠：规范路径除单独的 / 外，末尾不能带 /；用 join 而非手动在每项后加斜杠。

🔍 必测边界 Case

Case 1：仅根目录

path = "/" → "/"

Case 2：根上无法回退

path = "/../" → "/"（官方示例 4）

Case 3：多点目录名

path = "/.../a/../b/c/../d/./" → "/.../b/d"（官方示例 5）

Case 4：连续斜杠与尾随斜杠

path = "/home//foo/" → "/home/foo"（官方示例 1、2）