71. 简化路径
题目描述
输入字符串 path，它是 Unix 风格的绝对路径，以 / 开头。把它化简成规范路径后返回。
化简规则：. 代表当前目录，可以去掉；.. 代表回到上一级目录，已经在根目录时就停留在根目录；连续出现的多个 / 当作一个。除 . 和 .. 外，其他由点组成的名字，例如 ...，都当作普通目录名。
规范路径的格式：以一个 / 开头；相邻两个目录名之间恰好一个 /；末尾不带 /（结果只有根目录时就是 "/"）；路径中不再出现 . 或 ..。
示例 1
输入：path = "/home/" 输出："/home"
解释：去掉结尾多余的 /。
示例 2
输入：path = "/home//foo/" 输出："/home/foo"
解释：两个连续的 / 合并成一个。
示例 3
输入：path = "/home/user/Documents/../Pictures" 输出："/home/user/Pictures"
解释：.. 让路径从 Documents 退回 user，再进入 Pictures。
示例 4
输入：path = "/../" 输出："/"
解释：根目录没有上一级，.. 之后仍在根目录。
示例 5
输入：path = "/.../a/../b/c/../d/./" 输出："/.../b/d"
解释：... 是普通目录名；a 被 .. 抵消，c 被 .. 抵消，. 被忽略。
数据范围
1 <= path.length <= 3000path只含英文字母、数字、.、/和_。path是合法的 Unix 绝对路径。
解题思路
把路径按 / 切开，依次处理每一段：空串（多余的斜杠产生）和 . 直接跳过；.. 表示回到上一级，栈不空就弹出栈顶；其他名字表示进入子目录，压入栈。最后用 / 把栈中目录从底到顶连起来，前面加上 /。
为什么正确
处理完前若干段后，栈从底到顶正好是当前所在目录的完整路径。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
.. 遇到空栈时不能报错，也不能入栈。"..." 或 "..a" 不是特殊符号，要当作普通目录名入栈。栈为空时要返回 "/"，不能返回空串。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
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)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.pollLast();
}
} else {
stack.addLast(part);
}
}
return "/" + String.join("/", stack);
}
}class Solution {
public:
string simplifyPath(string path) {
vector<string> stack;
stringstream ss(path); string part;
while (getline(ss, part, '/')) {
if (part == "" || part == ".") {
continue;
}
if (part == "..") {
if (!stack.empty()) {
stack.pop_back();
}
} else {
stack.push_back(part);
}
}
string res;
for (auto& s : stack) res += "/" + s;
return res.empty() ? "/" : res;
}
};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, "/")
}var simplifyPath = function(path) {
const stack = [];
for (const part of path.split('/')) {
if (part === '' || part === '.') {
continue;
}
if (part === '..') {
if (stack.length) {
stack.pop();
}
} else {
stack.push(part);
}
}
return '/' + stack.join('/');
};function simplifyPath(path: string): string {
const stack: string[] = [];
for (const part of path.split('/')) {
if (part === '' || part === '.') {
continue;
}
if (part === '..') {
if (stack.length) {
stack.pop();
}
} else {
stack.push(part);
}
}
return '/' + stack.join('/');
}