0071. 简化路径【中等】
1. 📝 题目描述
给你一个字符串 path,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 '/' 开头),请你将其转化为 更加简洁的规范路径。
在 Unix 风格的文件系统中规则如下:
- 一个点
'.'表示当前目录本身。 - 此外,两个点
'..'表示将目录切换到上一级(指向父目录)。 - 任意多个连续的斜杠(即,
'//'或'///')都被视为单个斜杠'/'。 - 任何其他格式的点(例如,
'...'或'....')均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式:
- 始终以斜杠
'/'开头。 - 两个目录名之间必须只有一个斜杠
'/'。 - 最后一个目录名(如果存在)不能 以
'/'结尾。 - 此外,路径仅包含从根目录到目标文件或目录的路径上的目录(即,不含
'.'或'..')。
返回简化后得到的 规范路径。
示例 1:
txt
输入:path = "/home/"
输出:"/home"
解释:
应删除尾随斜杠。1
2
3
4
2
3
4
示例 2:
txt
输入:path = "/home//foo/"
输出:"/home/foo"
解释:
多个连续的斜杠被单个斜杠替换。1
2
3
4
2
3
4
示例 3:
txt
输入:path = "/home/user/Documents/../Pictures"
输出:"/home/user/Pictures"
解释:
两个点`".."`表示上一级目录(父目录)。1
2
3
4
2
3
4
示例 4:
txt
输入:path = "/../"
输出:"/"
解释:
不可能从根目录上升一级目录。1
2
3
4
2
3
4
示例 5:
txt
输入:path = "/.../a/../b/c/../d/./"
输出:"/.../b/d"
解释:
"..."在这个问题中是一个合法的目录名。1
2
3
4
2
3
4
提示:
1 <= path.length <= 3000path由英文字母,数字,'.','/'或'_'组成。path是一个有效的 Unix 风格绝对路径。
2. 🎯 s.1 - 栈
c
char* simplifyPath(char* path) {
int len = strlen(path);
char** stack = (char**)malloc(sizeof(char*) * len);
int top = 0;
char* token = strtok(path, "/");
while (token) {
if (strcmp(token, "..") == 0) {
if (top > 0) top--; // 返回上一级
} else if (strcmp(token, ".") != 0 && strlen(token) > 0) {
stack[top++] = token; // 有效目录名入栈
}
token = strtok(NULL, "/");
}
char* result = (char*)malloc(sizeof(char) * (len + 1));
result[0] = '\0';
if (top == 0) {
strcat(result, "/");
} else {
for (int i = 0; i < top; i++) {
strcat(result, "/");
strcat(result, stack[i]);
}
}
free(stack);
return result;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
js
/**
* @param {string} path
* @return {string}
*/
var simplifyPath = function (path) {
const stack = []
for (const part of path.split('/')) {
if (part === '..') {
stack.pop() // 返回上一级
} else if (part && part !== '.') {
stack.push(part) // 有效目录名入栈
}
}
return '/' + stack.join('/')
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
py
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
for part in path.split('/'):
if part == '..':
if stack: stack.pop() # 返回上一级
elif part and part != '.':
stack.append(part) # 有效目录名入栈
return '/' + '/'.join(stack)1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
- 时间复杂度:
,其中 n 是字符串 path 的长度 - 空间复杂度:
,栈最多存储所有目录名
算法思路:
- 以
'/'为分隔符拆分路径,逐段处理:".."→ 栈非空则弹出栈顶(返回上级)"."或空串 → 跳过- 其余 → 有效目录名,入栈
- 最后将栈中元素用
'/'拼接,加上前缀'/'即为简化路径