| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (44.20%) | 482 | - |
Tags
string | stack
Companies
facebook | microsoft
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/' 开头。 - 两个目录名之间必须只有一个斜杠
'/' 。 - 最后一个目录名（如果存在）不能 以
'/' 结尾。 - 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.' 或 '..'）。
返回简化后得到的 规范路径 。
示例 1：
1
2
3
| 输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
|
示例 2：
1
2
3
| 输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
|
示例 3：
1
2
3
| 输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
|
示例 4：
1
2
| 输入：path = "/a/./b/../../c/"
输出："/c"
|
提示：
1 <= path.length <= 3000path 由英文字母，数字，'.'，'/' 或 '_' 组成。path 是一个有效的 Unix 风格绝对路径。
Discussion | Solution
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public:
/**
## 解题思路
* 使用 stack记录每个dir;
* 用两个指针i,j 记录两个'/'之间的dir；
*/
string simplifyPath(string path) {
vector<string> dirs;
int i=0, j=0;
string curDir;
path = path + "/";
while(j<path.length()) {
if (path[j] == '/') {
if (j>i) {
curDir = path.substr(i, j-i);
if (curDir == ".") {
//
} else if (curDir == "..") {
if (dirs.size()>0) {
dirs.pop_back();
}
} else {
dirs.push_back(curDir);
}
}
i=j+1;
}
j++;
}
string res;
if (dirs.size()>0) {
for(auto dir: dirs) {
res += "/" + dir;
}
} else {
res = "/";
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| // @lc code=start
impl Solution {
/// ## 解题思路
/// - stack
pub fn simplify_path(path: String) -> String {
format!(
"/{}",
path.split('/')
.filter(|&x| x != "" && x != ".")
.fold(vec![], |mut s, x| {
if x == ".." {
s.pop();
} else {
s.push(x);
}
s
})
.join("/")
)
}
}
// @lc code=end
struct Solution;
|