LeetCode 71: Simplify Path (Canonical Stack Normalization)
LeetCode 71StackStringSimulationToday we solve LeetCode 71 - Simplify Path.
Source: https://leetcode.com/problems/simplify-path/
English
Problem Summary
Given an absolute UNIX path, return its canonical form. Rules: single slash separators, no trailing slash (except root), . means current directory, and .. moves to parent when possible.
Key Insight
Process each path token once and maintain a stack of valid directory names. Regular token => push, .. => pop if available, empty token / . => ignore.
Brute Force and Limitations
Repeatedly replacing //, /./, or scanning backward for each .. can become messy and error-prone. A stack gives a direct simulation of directory navigation with clean boundaries.
Optimal Algorithm Steps
1) Split by /.
2) Skip empty tokens and ..
3) If token is .., pop stack when non-empty.
4) Otherwise push directory token.
5) Join stack with / and prepend leading slash; if empty, return /.
Complexity Analysis
Time: O(n).
Space: O(n) in the worst case for stack storage.
Common Pitfalls
- Treating multiple slashes as different levels.
- Popping below root for excessive ...
- Forgetting root case when stack is empty.
- Accidentally preserving trailing slash.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
String[] parts = path.split("/");
for (String part : parts) {
if (part.isEmpty() || part.equals(".")) {
continue;
}
if (part.equals("..")) {
if (!stack.isEmpty()) stack.removeLast();
} else {
stack.addLast(part);
}
}
if (stack.isEmpty()) return "/";
StringBuilder sb = new StringBuilder();
for (String dir : stack) {
sb.append('/').append(dir);
}
return sb.toString();
}
}import "strings"
func simplifyPath(path string) string {
parts := strings.Split(path, "/")
stack := make([]string, 0, len(parts))
for _, p := range parts {
if p == "" || p == "." {
continue
}
if p == ".." {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, p)
}
}
if len(stack) == 0 {
return "/"
}
return "/" + strings.Join(stack, "/")
}class Solution {
public:
string simplifyPath(string path) {
vector<string> st;
string token;
stringstream ss(path);
while (getline(ss, token, '/')) {
if (token.empty() || token == ".") continue;
if (token == "..") {
if (!st.empty()) st.pop_back();
} else {
st.push_back(token);
}
}
if (st.empty()) return "/";
string ans;
for (const string& dir : st) {
ans += "/" + dir;
}
return ans;
}
};class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for token in path.split('/'):
if token == '' or token == '.':
continue
if token == '..':
if stack:
stack.pop()
else:
stack.append(token)
return '/' + '/'.join(stack) if stack else '/'var simplifyPath = function(path) {
const stack = [];
for (const token of path.split('/')) {
if (token === '' || token === '.') continue;
if (token === '..') {
if (stack.length > 0) stack.pop();
} else {
stack.push(token);
}
}
return stack.length === 0 ? '/' : '/' + stack.join('/');
};中文
题目概述
给你一个绝对路径，要求转换成 UNIX 规范路径：目录之间仅保留一个斜杠、末尾不带斜杠（根目录除外）、. 表示当前目录、.. 表示返回上一级目录。
核心思路
把路径按 / 切分后顺序处理，用栈维护“当前有效目录链”。普通目录入栈，.. 出栈（若非空），空串和 . 直接忽略。
暴力解法与不足
若靠字符串反复替换或在每次遇到 .. 时向前回扫，边界会非常多（连续斜杠、根目录、结尾斜杠），实现容易混乱。栈模拟目录跳转更稳。
最优算法步骤
1）按 / 分割路径。
2）跳过空 token 与 .。
3）遇到 .. 且栈非空时弹栈。
4）其余 token 入栈。
5）最终用 / 拼接栈内容并加前导斜杠；若栈空返回 /。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)（最坏情况下栈保存全部目录名）。
常见陷阱
- 把连续斜杠误当成多层目录。
- .. 过多时错误地越过根目录。
- 栈空时没正确返回根路径 /。
- 结果末尾残留多余斜杠。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<>();
String[] parts = path.split("/");
for (String part : parts) {
if (part.isEmpty() || part.equals(".")) {
continue;
}
if (part.equals("..")) {
if (!stack.isEmpty()) stack.removeLast();
} else {
stack.addLast(part);
}
}
if (stack.isEmpty()) return "/";
StringBuilder sb = new StringBuilder();
for (String dir : stack) {
sb.append('/').append(dir);
}
return sb.toString();
}
}import "strings"
func simplifyPath(path string) string {
parts := strings.Split(path, "/")
stack := make([]string, 0, len(parts))
for _, p := range parts {
if p == "" || p == "." {
continue
}
if p == ".." {
if len(stack) > 0 {
stack = stack[:len(stack)-1]
}
} else {
stack = append(stack, p)
}
}
if len(stack) == 0 {
return "/"
}
return "/" + strings.Join(stack, "/")
}class Solution {
public:
string simplifyPath(string path) {
vector<string> st;
string token;
stringstream ss(path);
while (getline(ss, token, '/')) {
if (token.empty() || token == ".") continue;
if (token == "..") {
if (!st.empty()) st.pop_back();
} else {
st.push_back(token);
}
}
if (st.empty()) return "/";
string ans;
for (const string& dir : st) {
ans += "/" + dir;
}
return ans;
}
};class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for token in path.split('/'):
if token == '' or token == '.':
continue
if token == '..':
if stack:
stack.pop()
else:
stack.append(token)
return '/' + '/'.join(stack) if stack else '/'var simplifyPath = function(path) {
const stack = [];
for (const token of path.split('/')) {
if (token === '' || token === '.') continue;
if (token === '..') {
if (stack.length > 0) stack.pop();
} else {
stack.push(token);
}
}
return stack.length === 0 ? '/' : '/' + stack.join('/');
};
Comments