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路径字符串。使用栈数据结构，扫描字符串，获取/之前的字符串，如果是一点.则保持当前路径，什么也不做；如果是两点..则弹栈，否则把字符串压栈。 需要注意的是/../，/.，/…等情况，三个点应该认为一个合法的路径字符串，虽然在Windows上并不合法。所以我们在进行算法之前，不管原始字符串末尾是否包含/，我们都在末尾添加上斜杠/，以便后续统一处理。 扫描完一次字符串之后，把栈内字符串依次弹出并组合成一个简化的路径。 完整代码如下：
class Solution {
public:
string simplifyPath(string path)
{
path += "/";
stack<string> sPath;
string p1 = "";
for (int i = 0; i < path.size(); i++) {
if (path[i] == ‘/’) {
if (p1 == "" || p1 == ".") {
}
else if (p1 == "..") {
if (!sPath.empty())
sPath.pop();
}
else {
sPath.push(p1);
}
p1 = "";
}
else
p1 += path[i];
}
if (sPath.empty())
return "/";
string ans = "";
while (!sPath.empty()) {
ans = "/" + sPath.top() + ans;
sPath.pop();
}
return ans;
}
};本代码提交AC，用时6MS。
二刷。更简洁代码：
class Solution {
public:
string simplifyPath(string path) {
stack<string> stk;
int n = path.size();
int i = 0, j = 0;
while (i < n) {
while (i < n&&path[i] == '/')++i;
if (i >= n)break;
j = i + 1;
while (j < n&&path[j] != '/')++j;
string name = path.substr(i, j - i);
if (name == ".." && !stk.empty())stk.pop();
if (name != "."&&name != "..")stk.push(name);
i = j;
}
string ans = "";
while (!stk.empty()) {
ans = "/" + stk.top() + ans;
stk.pop();
}
if (ans == "")return "/";
else return ans;
}
};本代码提交AC，用时8MS。