71 Simplify Path

1. Question

Given an absolute path for a file (Unix-style), simplify it.
For example, path="/home/", =>"/home" path="/a/./b/../../c/", =>"/c"
Corner Cases:
  • Did you consider the case where path ="/../"? In this case, you should return"/"
  • Another corner case is the path might contain multiple slashes '/'together, such as"/home//foo/"In this case, you should ignore redundant slashes and return "/home/foo".

2. Implementation

思路:根据题目的例子,我们知道" ", ".", ".."这三种情况不会出现在结果里,所以把它们存在HashSet里。如果我们遇到"..", 我们需要返回上一级目录,所以需要利用stack。最后需要将stack的结果用“/"隔开,注意stack存储结果的顺序和实际的结果是相反的。
1
class Solution {
2
public String simplifyPath(String path) {
3
Set<String> set = new HashSet<>();
4
set.add(".");
5
set.add("..");
6
set.add("");
7
8
Stack<String> stack = new Stack<>();
9
10
for (String dir : path.split("/")) {
11
if (dir.equals("..") && !stack.isEmpty()) {
12
stack.pop();
13
}
14
else if (!set.contains(dir)) {
15
stack.push(dir);
16
}
17
}
18
19
StringBuilder res = new StringBuilder();
20
while (!stack.isEmpty()) {
21
res.insert(0, stack.pop());
22
res.insert(0, "/");
23
}
24
return res.length() == 0 ? "/" : res.toString();
25
}
26
}
Copied!

3. Time & Space Complexity

时间和空间都是O(n)