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
| class Solution {
public String simplifyPath(String path) {
Deque<String> deque = new ArrayDeque<>();
int ptr = 0;
while (ptr < path.length()) {
while (ptr < path.length() && path.charAt(ptr) == '/') {
ptr += 1;
}
if (ptr == path.length()) {
break;
}
StringBuilder currSub = new StringBuilder();
while (ptr < path.length() && path.charAt(ptr) != '/') {
currSub.append(path.charAt(ptr));
ptr += 1;
}
String s = currSub.toString();
if (s.equals("..")) {
if (!deque.isEmpty()) {
deque.pollLast();
}
} else if (!s.equals(".")) {
deque.offerLast(s);
}
}
StringBuilder ans = new StringBuilder();
while (!deque.isEmpty()) {
ans.append("/").append(deque.pollFirst());
}
return ans.length() == 0 ? "/" : ans.toString();
}
}
|
不用自带的split的做法. 第19行很关键, 不能把if条件写成等于..而且deque不为空, 因为假如等于..但是deque为空, 我们就会进入下面的else if里面去. 于是我们需要把deque不为空写到等于..后的if条件里面.
为什么想到会用栈? 因为有..表明我们要返回上一层, 那就要记录上一层是什么, 那如果继续呢? 那还要记录, 因此想到了栈. 到达哪里把经过的地方都记录在栈中, 如果.., 那就把栈顶的元素pop即可.
时间复杂度: O(n)
空间复杂度: O(n) 用了stack.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public String simplifyPath(String path) {
Set<String> specialStrings = new HashSet<>(Arrays.asList("..", ".", ""));
Deque<String> deque = new ArrayDeque<>();
for (String s : path.split("/")) {
if (s.equals("..") && !deque.isEmpty()) {
deque.pollLast();
} else if (!specialStrings.contains(s)) {
deque.offerLast(s);
}
}
StringBuilder ans = new StringBuilder();
while (!deque.isEmpty()) {
ans.append("/")
.append(deque.pollFirst());
}
return ans.length() == 0 ? "/" : ans.toString();
}
}
|
这是用split method的做法. else if里面那个条件很好, 我们这里是把等于..和deque不为空写到了一个if条件里面, 如果它不满足, 就表示要么deque为空, 要么s不为.. 于是我们只有在s不是..以及.或者“”的时候才把当前的s压入deque中.
时间复杂度: O(n)
空间复杂度: O(n)
