LeetCode 0071 - Simplify Path
# Hints
- 模拟 + 栈
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path .
In a UNIX-style file system, a period .
refers to the current directory. Furthermore, a double period ..
moves the directory up a level.
Note that the returned canonical path must always begin with a slash /
, and there must be only a single slash /
between two directory names. The last directory name (if it exists) must not end with a trailing /
. Also, the canonical path must be the shortest string representing the absolute path.
Example 1:
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.
Example 3:
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:
Input: "/a/./b/../../c/"
Output: "/c"
Example 5:
Input: "/a/../../b/../c//.//"
Output: "/c"
Example 6:
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
# 题意
给定一个 UNIX 文件系统的绝对路径,根据题意将其化简。
# 题解
根据题意模拟即可。我们在遍历并解析路径的同时用栈来记录每一级路径,这样可以很方便地处理 ..
的回退操作,最后逆序生成结果串即可。
细节问题:
- 注意处理化简结果为空串的情况。
# AC代码
class Solution {
public:
string simplifyPath(const string & path) {
// 解析
vector<string> stk;
string cur;
for (int i = 0; i <= path.length(); i ++) {
// 获取
if (i < path.length() && path[i] != '/') {
cur += path[i];
continue;
}
// 截取
if (cur == "..") {
if (!stk.empty()) {
stk.pop_back();
}
} else if (cur != "." && !cur.empty()) {
stk.push_back(cur);
}
cur.clear();
}
// 生成
string res;
for (auto str : stk) {
res += "/" + str;
}
if (res.empty()) {
res += "/";
}
// 返回
return res;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01