http://www.programcreek.com/2014/04/leetcode-simplify-path-java/
https://leetcode.com/problems/simplify-path/discuss/25778/Java-easy-to-understand-Stack-solution.
https://leetcode.com/discuss/22592/java-10-lines-solution-with-stack
public String simplifyPath(String path) { StringBuilder sb = new StringBuilder("/"); LinkedList<String> stack = new LinkedList<String>(); for(String s: path.split("/")){ if(s.equals("..")){ if(!stack.isEmpty()) stack.removeLast(); } else if(!s.equals("") && !s.equals(".")) stack.add(s); } for(String s: stack){ sb.append(s+"/"); } if(!stack.isEmpty()) sb.setLength(sb.length()-1);//remove last / return sb.toString(); }
http://www.cnblogs.com/springfor/p/3869666.html
1 public String simplifyPath(String path) {
2 if(path == null||path.length()==0)
3 return path;
4
5 Stack<String> stack = new Stack<String>();
6 String[] list = path.split("/");
7
8 for(int i=0; i<list.length; i++){
9 if(list[i].equals(".")||list[i].length()==0)
10 continue;
11 else if(!list[i].equals(".."))
12 stack.push(list[i]);
13 else{
14 if(!stack.isEmpty())
15 stack.pop();
16 }
17 }
18
19 StringBuilder res = new StringBuilder();
20
21 Stack<String> temp = new Stack<String>();
22 while(!stack.isEmpty())
23 temp.push(stack.pop());
24
25 while(!temp.isEmpty())
26 res.append("/"+temp.pop());
27
28 if(res.length()==0)
29 res.append("/");
30
31 return res.toString();
32 }
Use StringBuilder
https://leetcodenotes.wordpress.com/2013/10/31/leetcode-simplify-path-unix%E7%BB%9D%E5%AF%B9%E8%B7%AF%E5%BE%84simplify/
Why "/.." should return "/" but not "/.."?
https://leetcode.com/discuss/92213/java-solution-without-using-build-split-function-beats-over
Given an absolute path for a file (Unix-style), simplify it.
path = "/home/", => "/home" path = "/a/./b/../../c/", => "/c" path = "/../", => "/" path = "/home//foo/", => "/home/foo"https://leetcode.com/discuss/9580/my-o-n-ac-code-just-need-to-handle-two-special-cases
I think It is better to use deque since it provides the convenience to output elements from both sides.
public String simplifyPath(String path) {
if (path==null||path.length()==0) return "";
String[] paths = path.split("/+");
Deque<String> queue = new LinkedList<String>();
for (String s:paths){
if (s.equals("..")){
if (!queue.isEmpty())
queue.pollLast();
}
else if (s.equals(".")||s.equals(""))
continue;
else queue.offer(s);
}
StringBuilder result=new StringBuilder("");
if (queue.isEmpty()) result.append("/");
while (!queue.isEmpty()){
result.append("/").append(queue.poll());//Faster than string manipulation.
}
return result.toString();
}
https://leetcode.com/discuss/33395/ac-solution-in-javahttps://leetcode.com/problems/simplify-path/discuss/25778/Java-easy-to-understand-Stack-solution.
https://leetcode.com/discuss/22592/java-10-lines-solution-with-stack
public String simplifyPath(String path) { StringBuilder sb = new StringBuilder("/"); LinkedList<String> stack = new LinkedList<String>(); for(String s: path.split("/")){ if(s.equals("..")){ if(!stack.isEmpty()) stack.removeLast(); } else if(!s.equals("") && !s.equals(".")) stack.add(s); } for(String s: stack){ sb.append(s+"/"); } if(!stack.isEmpty()) sb.setLength(sb.length()-1);//remove last / return sb.toString(); }
One small comment, since you are using Deque, why not take advantage of [pool|peek]Last() methods in order to be able to use stringBuilder?
StringBuilder sb = new StringBuilder();
while (path.peekLast() != null) {
sb.append('/');
sb.append(path.pollLast());
}http://www.cnblogs.com/springfor/p/3869666.html
要注意split函数是可以split出空字符的，例如：//b/ 会被split结果为["","b"]。
最后使用StringBuilder进行拼接，由于String在每次对字符串修改时候均会生成一个新的String，效率较低，一般会采用StringBuilder来进行字符串修改的操作
这是一道简化路径的题，路径简化的依据是：
当遇到“/../"则需要返回上级目录，需检查上级目录是否为空。
当遇到"/./"则表示是本级目录，无需做任何特殊操作。
当遇到"//"则表示是本级目录，无需做任何操作。
当遇到其他字符则表示是文件夹名，无需简化。
当字符串是空或者遇到”/../”，则需要返回一个"/"。
当遇见"/a//b"，则需要简化为"/a/b"。
根据这些要求，我需要两个栈来解决问题。
先将字符串依"/"分割出来，然后检查每个分割出来的字符串。
当字符串为空或者为"."，不做任何操作。
当字符串不为".."，则将字符串入栈。
当字符串为"..", 则弹栈（返回上级目录）。
当对所有分割成的字符串都处理完后，检查第一个栈是否为空，如果栈为空，则证明没有可以重建的目录名，返回"/"即可。
当第一个栈不为空时，这时候我们需要还原path。但是不能弹出栈，因为按照要求栈底元素应该为最先还原的目录path。
例如：原始path是 /a/b/c/，栈里的顺序是：a b c，如果依次弹栈还原的话是：/c/b/a（错误！），正确答案为：/a/b/c
所以这里我应用了第二个栈，先将第一个栈元素弹出入栈到第二个栈，然后再利用第二个栈还原回初始path。
1 public String simplifyPath(String path) {
2 if(path == null||path.length()==0)
3 return path;
4
5 Stack<String> stack = new Stack<String>();
6 String[] list = path.split("/");
7
8 for(int i=0; i<list.length; i++){
9 if(list[i].equals(".")||list[i].length()==0)
10 continue;
11 else if(!list[i].equals(".."))
12 stack.push(list[i]);
13 else{
14 if(!stack.isEmpty())
15 stack.pop();
16 }
17 }
18
19 StringBuilder res = new StringBuilder();
20
21 Stack<String> temp = new Stack<String>();
22 while(!stack.isEmpty())
23 temp.push(stack.pop());
24
25 while(!temp.isEmpty())
26 res.append("/"+temp.pop());
27
28 if(res.length()==0)
29 res.append("/");
30
31 return res.toString();
32 }
在网上还看到有人写的最后还原path没用到第二个栈，是因为可以利用Java中LinkedList 数据类型来表示第一个栈。LinkedList数据类型很强大，包含了栈和队列的实现。所以最后还原时调用removeLast()函数就可以解决顺序问题。
1 public static String simplifyPath(String path) {
2 if(path.length() == 0){
3 return path;
4 }
5
6 String[] splits = path.split("/");
7 LinkedList<String> stack = new LinkedList<String>();
8 for (String s : splits) {
9 if(s.length()==0 || s.equals(".")){
10 continue;
11 }else if(s.equals("..")){
12 if(!stack.isEmpty()){
13 stack.pop();
14 }
15 }else{
16 stack.push(s);
17 }
18 }
19
20 if(stack.isEmpty()){
21 stack.push("");
22 }
23 String ret = "";
24 while(!stack.isEmpty()){
25 ret += "/" + stack.removeLast();
26 }
27
28 return ret;
29 }
http://www.jiuzhang.com/solutions/simplify-path/2 if(path.length() == 0){
3 return path;
4 }
5
6 String[] splits = path.split("/");
7 LinkedList<String> stack = new LinkedList<String>();
8 for (String s : splits) {
9 if(s.length()==0 || s.equals(".")){
10 continue;
11 }else if(s.equals("..")){
12 if(!stack.isEmpty()){
13 stack.pop();
14 }
15 }else{
16 stack.push(s);
17 }
18 }
19
20 if(stack.isEmpty()){
21 stack.push("");
22 }
23 String ret = "";
24 while(!stack.isEmpty()){
25 ret += "/" + stack.removeLast();
26 }
27
28 return ret;
29 }
Use StringBuilder
String result = "/"; String[] stubs = path.split("/+"); ArrayList<String> paths = new ArrayList<String>(); for (String s : stubs){ if(s.equals("..")){ if(paths.size() > 0){ paths.remove(paths.size() - 1); } } else if (!s.equals(".") && !s.equals("")){ paths.add(s); } } for (String s : paths){ result += s + "/"; } if (result.length() > 1) result = result.substring(0, result.length() - 1); return result; }http://rleetcode.blogspot.com/2014/01/simplify-path-java.html
https://leetcodenotes.wordpress.com/2013/10/31/leetcode-simplify-path-unix%E7%BB%9D%E5%AF%B9%E8%B7%AF%E5%BE%84simplify/
public String simplifyPath(String path) {
Stack<String> s = new Stack<String>();
String[] split = path.split("/");
for (String a : split) {
if (!a.equals(".") && !a.isEmpty()) {
if (a.equals("..")) {
if (!s.isEmpty()) {
s.pop();
}
} else {
s.push(a);
}
}
}
StringBuilder sb = new StringBuilder();
while (!s.isEmpty()) {
sb.insert(0, s.pop());
sb.insert(0, "/");
}
return sb.length() == 0 ? "/" : sb.toString();
}
https://leetcode.com/discuss/22209/why-should-return-but-notWhy "/.." should return "/" but not "/.."?
I would say it is a rule for canonical path, removing all redundant name from path (such as relative path name : ".", "..").
In this case, ".." means the parent dir while there is no parent dir for a root dir. So the root path "/" is the canonical path for "/..", "/./..", "/../.", etc.
X.https://leetcode.com/discuss/92213/java-solution-without-using-build-split-function-beats-over
When we encounter "/", we try to find the next "/" and get the string between them. If it equals ".." and the stack is not empty, then we pop one element. If it does not equal "." and is not empty, then we can push it into the stack.
public String simplifyPath(String path) {
StringBuilder sb = new StringBuilder();
Stack<String> stack = new Stack<>();
int i = 0, len = path.length();
while (i < len) {
if (path.charAt(i) == '/') {
int j = i+1;
while (j < len && path.charAt(j) != '/') {
j++;
}
String current = path.substring(i+1, j);
if (current.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
if (!current.equals(".") && !current.equals("")) {
stack.push(current);
}
}
i = j;
}
}
for (String s : stack) {
sb.append("/"+s);
}
return sb.length() == 0 ? "/" : sb.toString();
}
}