- Simplify Path:题目链接
方法1：Stack
基本思想：/:表示的时分隔符.:表示当前路径..:表示上一层路径
For example,
path = “/home/“, => “/home”
path = “/a/./b/../../c/“, => “/c”
path = “/a/../../b/../c//.//“, => “/c”
path = “/a//b////c/d//././/..”, => “/a/b/c”
可以用split(“/“)以”/“分隔，举个列子：
“/a//b////c/d//././/..” —> [, a, , b, , , , c, d, , ., ., , ..]
遍历，如果遇到"",. 直接跳过，遇上".."出栈,最后将栈内元素从栈底向栈顶打印
AC代码：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
33import java.util.Arrays;
import java.util.Stack;
class Solution {
// 时间复杂度(N) 空间复杂度O(m) m:path.length
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] arr = path.split("/"); // 将path以“/”划分的结果放到arr[]字符串数组中
for (int i = 0; i < arr.length; ++i) { // 遍历
if ((arr[i].equals("") || arr[i].equals("."))) { // 如果遇上"" || "." 跳过
continue;
}
if (!arr[i].equals("..")){ // 遇上路径名 入栈
stack.push(arr[i]);
}
if (arr[i].equals("..") && stack.size() != 0) { // 遇上".." 将栈顶元素出栈
stack.pop();
}
}
StringBuffer sb = new StringBuffer();
for (String s : stack) { // 从栈底遍历栈 不是从栈顶出栈的方式
sb.append("/" + s);
}
return stack.size() == 0 ? "/" : sb.toString(); // 如果栈空 返回 "/"
}
public static void main(String[] args) {
System.out.println(new Solution().simplifyPath("/."));
System.out.println(new Solution().simplifyPath("/a/../../b/../c//.//"));
}
}
pS:源代码链接