LeetCode 71. 简化路径
目录
题目描述
✅ 71. 简化路径
题意分析
输入是一条 Unix 风格的绝对路径，一定以
/开头；输出是它化简之后的规范写法。要处理的记号一共四类：单个
.表示「当前目录」，对结果没有任何影响；..表示「回到上一级目录」；连续出现的多个/与单个/完全等价，它们之间夹出来的空片段应当直接丢弃；除此之外的片段一律按普通目录名对待。约束里还有两条容易被忽略的规则。其一，路径已经处在根目录时再遇到
..，只能停留在根目录，不允许产生/..这样的结果；其二，返回值必须以单个/开头，并且除根目录本身以外，结尾不能带/。边界情形有：输入就是
"/"；输入是"/../"这种一路退到顶的路径；输入是"/home//foo/"这种带连续斜杠和结尾斜杠的路径；以及...、....这类由多个点组成、但按题意只是普通合法目录名的片段。
解法：栈模拟目录进出
核心思路
..总是撤销最近一个尚未被撤销的目录，符合后进先出，因此用栈保存当前有效的目录序列。按/切分后，空片段和.不改变位置；..在栈非空时弹出栈顶；其他片段（包括...）都是普通目录名，直接入栈。循环不变量是：处理完任意前缀后，栈从底到顶恰好是该前缀化简后的目录序列。三类操作分别对应“不变、删除末项、追加末项”，都能维持不变量；扫描结束后栈就是完整路径的规范目录序列。最后在目录间补
/，空栈自然得到根目录/。
解题步骤
- 按
/切分路径，连续斜杠产生的空片段统一在遍历中忽略。- 遇到空串或
.，跳过；遇到..，仅在栈非空时弹出栈顶，避免越过根目录。- 其余片段全部入栈，不能把
.hidden、...等名称误判成特殊记号。- 用
/连接栈中目录，并在开头补/。例如
"/a/./b/../../c/"的栈依次为[a] → [a,b] → [a] → [] → [c]，结果是"/c"；"/../../"始终保持空栈，结果是"/"。
代码实现
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
for (String part : path.split("/")) {
if (part.isEmpty() || part.equals(".")) {
continue;
}
if (part.equals("..")) {
if (!stack.isEmpty()) {
stack.removeLast();
}
} else {
stack.addLast(part);
}
}
return "/" + String.join("/", stack);
}
}
import "strings"
func simplifyPath(path string) string {
stack := []string{}
for _, part := range strings.Split(path, "/") {
if part == "" || part == "." {
continue
}
if part == ".." {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, part)
}
}
return "/" + strings.Join(stack, "/")
}
复杂度分析
- 时间复杂度：$O(n)$。切分、遍历和拼接都只线性处理路径字符，每个目录最多入栈、出栈一次。
- 空间复杂度：$O(n)$。切分结果和栈最多保存与输入等量的字符。
关键点总结
- 看到“撤销最近一个有效目录”，应立即联想到栈。
- 栈保存的是目录名，不保存
/；分隔符只在最终拼接时补回。- 只有完整片段
.和..有特殊含义，其他带点名称都是普通目录。- 面试时先说清“栈等于已处理前缀的规范路径”这一不变量，再按三类片段写分支，代码会很自然。
易错点总结
- 弹栈前不判空：
"/../"会越界；根目录上方的..应直接忽略。- 用“以点开头”判断特殊片段：
"/.hidden/..."中两段都应保留，只有.、..本身特殊。- 不跳过空片段：
"/home//foo/"会错误保留连续斜杠。- 从栈顶逆序拼接：
"/a/b"会得到"/b/a"；输出顺序必须是栈底到栈顶。- 空栈返回空串：
"/../../"的规范结果是根目录"/"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 20. 有效的括号 | 简单 | 栈判断配对，只需合法性不需还原 |
| 1047. 删除字符串中的所有相邻重复项 | 简单 | 抵消条件是「与栈顶相同」而非固定记号 |
| 150. 逆波兰表达式求值 | 中等 | 栈存操作数，遇运算符弹两个再压回 |
| 388. 文件的最长绝对路径 | 中等 | 用缩进深度而非 .. 驱动栈的伸缩 |
| 394. 字符串解码 | 中等 | 双栈保存倍数与前缀，处理嵌套结构 |