05 August 2008
把unix path按照规则简化 路径
给一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//’）都被视为单个斜杠 ‘/’ 。 对于此问题，任何其他格式的点（例如，’…‘）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
1
2
3
4
始终以斜杠 '/' 开头。
两个目录名之间必须只有一个斜杠 '/' 。
最后一个目录名（如果存在）不能 以 '/' 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。
返回简化后得到的 规范路径 。
根据题意，使用栈进行模拟即可。
具体的，从前往后处理 path，每次以 item 为单位进行处理（有效的文件名），根据 item 为何值进行分情况讨论：
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
34
35
36
class Solution {
public String simplifyPath(String path) {
if (path == null || path.trim().isEmpty()) {
return "";
}
int len = path.length();
Deque<String> deque = new ArrayDeque<>();
for (int left = 1; left < len; ) {
if (path.charAt(left) == '/') {
left++; // 第一个"/"特殊处理
continue;
}
int right = left + 1;
while (right < len && path.charAt(right) != '/') {
right++;
}
String item = path.substring(left, right); // 到right == '/'为止
if (item.equals("..")) {
if (!deque.isEmpty()) { // 双端队列里面还有东西，不是root
deque.pollLast();
}
} else if (!item.equals(".")) { // 等于"."时不做任何处理
deque.addLast(item);
}
left = right;
}
StringBuilder sb = new StringBuilder();
while (!deque.isEmpty()) {
sb.append("/").append(deque.pollFirst());
}
return sb.length() == 0 ? "/" : sb.toString();
}
}
另外写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] pathArr = path.split("/");
for (String s : pathArr) {
if (!stack.empty() && s.equals("..")) {
stack.pop();
} else if (!s.equals(".") && !s.equals("") && !s.equals("..")) {
stack.push(s);
}
}
List<String> list = new ArrayList(stack);
return "/" + String.join("/", list);
}
}