## 题目地址

https://leetcode.com/problems/simplify-path/

## 题目描述

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. For more information, see: Absolute path vs relative path in Linux/Unix

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"

## 代码

C++ 解法一:

``````class Solution {
public:
string simplifyPath(string path) {
vector<string> v;
int i = 0;
while (i < path.size()) {
while (path[i] == '/' && i < path.size()) ++i;
if (i == path.size()) break;
int start = i;
while (path[i] != '/' && i < path.size()) ++i;
int end = i - 1;
string s = path.substr(start, end - start + 1);
if (s == "..") {
if (!v.empty()) v.pop_back();
} else if (s != ".") {
v.push_back(s);
}
}
if (v.empty()) return "/";
string res;
for (int i = 0; i < v.size(); ++i) {
res += '/' + v[i];
}
return res;
}
};

``````

C 解法一:

``````class Solution {
public:
string simplifyPath(string path) {
vector<string> v;
char *cstr = new char[path.length() + 1];
strcpy(cstr, path.c_str());
char *pch = strtok(cstr, "/");
while (pch != NULL) {
string p = string(pch);
if (p == "..") {
if (!v.empty()) v.pop_back();
} else if (p != ".") {
v.push_back(p);
}
pch = strtok(NULL, "/");
}
if (v.empty()) return "/";
string res;
for (int i = 0; i < v.size(); ++i) {
res += '/' + v[i];
}
return res;
}
};

``````

C++中也有专门处理字符串的机制，我们可以使用stringstream来分隔字符串，然后对每一段分别处理，思路和上面的方法相似，参见代码如下：

C++ 解法二：

``````class Solution {
public:
string simplifyPath(string path) {
string res, t;
stringstream ss(path);
vector<string> v;
while (getline(ss, t, '/')) {
if (t == "" || t == ".") continue;
if (t == ".." && !v.empty()) v.pop_back();
else if (t != "..") v.push_back(t);
}
for (string s : v) res += "/" + s;
return res.empty() ? "/" : res;
}
};

``````

Java 解法二：

``````public class Solution {
public String simplifyPath(String path) {
Stack<String> s = new Stack<>();
String[] p = path.split("/");
for (String t : p) {
if (!s.isEmpty() && t.equals("..")) {
s.pop();
} else if (!t.equals(".") && !t.equals("") && !t.equals("..")) {
s.push(t);
}
}
List<String> list = new ArrayList(s);
return "/" + String.join("/", list);
}
}
``````

评论
0 评论