LeetCode - Simplify Path
Problem description
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:
1
2
3
Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.
Example 2:
1
2
3
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:
1
2
3
Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.
Example 4:
1
2
Input: "/a/./b/../../c/"
Output: "/c"
Example 5:
1
2
Input: "/a/../../b/../c//.//"
Output: "/c"
Example 6:
1
2
Input: "/a//b////c/d//././/.."
Output: "/a/b/c"
Analysis
It’s a stack related problem.
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
public String simplifyPath(String path) {
//path = path.replaceAll("/+", "/");
String[] array = path.split("/");
List<String> list = new ArrayList<>();
for (String s:array){
if (s.equals(".")){
continue;
}
if (s.equals("..")){
if (list.size() != 0){
list.remove(list.size() - 1);
}
}
else if (!s.isEmpty()){
list.add(s);
}
}
StringBuilder sb = new StringBuilder();
for(String s:list){
sb.append("/");
sb.append(s);
}
if (sb.length() == 0){
sb.append("/");
}
return sb.toString();
}
What to improve
- regex use a lot of time, we should not use it if possible.