Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
The simplification of an absolute path can be done by first separating the path by "/" and interpreting each segment as subdirectory, current directory, or its parent directory. For ease of going back to the parent directory, we can use a stack to which a segment is pushed as long as it represents a subdirectory. Finally, the stack is converted into an array, and the simplified path is the concatenation of the segments in the stack preceded by a "/".
http://zjalgorithm.blogspot.com/2014/11/leetcode-simplify-path-java.html
LinkedList, first is used as stack: /a/b ==> a,b, then iterative it ==> same as reverse the stack.
http://rleetcode.blogspot.com/2014/01/simplify-path-java.html
http://stupidcodergoodluck.wordpress.com/2013/11/16/leetcode-simplify-path/
Read full article from LeetCode - Simplify Path | Darren's Blog
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
The simplification of an absolute path can be done by first separating the path by "/" and interpreting each segment as subdirectory, current directory, or its parent directory. For ease of going back to the parent directory, we can use a stack to which a segment is pushed as long as it represents a subdirectory. Finally, the stack is converted into an array, and the simplified path is the concatenation of the segments in the stack preceded by a "/".
http://zjalgorithm.blogspot.com/2014/11/leetcode-simplify-path-java.html
LinkedList, first is used as stack: /a/b ==> a,b, then iterative it ==> same as reverse the stack.
public static String simplifyPath(String path) { LinkedList<String> stack = new LinkedList<String>(); String[] pathsplit = path.split("/"); for(String p : pathsplit) { if( p.equals("..") && !stack.isEmpty() ) { // stack pop stack.removeLast(); } else if(p.length()!=0 && !p.equals(".") && !p.equals("..")) { stack.addLast(p); // stack push } // other cases: do nothing } StringBuilder sb = new StringBuilder(); if(stack.isEmpty()) return "/"; //!!! corner case for(String p : stack) { // build output sb.append("/"); sb.append(p); } return sb.toString();}public String simplifyPath(String path) {StringBuilder result=new StringBuilder();if (path==null ||path.length()==0){return result.toString();}String[] strs=path.split("/");Stack<String> stack=new Stack<String>();for (String s: strs){if (s.length()==0 ||s.equals(".")){}else if (s.equals("..")){if (!stack.isEmpty()){stack.pop();}}else{stack.push(s);}}if (stack.isEmpty()){result.append('/');}else{while (!stack.isEmpty()){// performace is not good here: char[] value insert at front.result.insert(0, stack.pop());result.insert(0, '/');}}return result.toString();}
public String simplifyPath(String path) {
if (path == null)
return null;
if (path.length() == 0)
return "/";
int n = path.length();
Stack<String> stack = new Stack<String>();// use LinkedList as stack
String[] directories = path.split("/"); // Separate path by "/"
for (String dir : directories) {
if (dir.length() != 0) {
if (dir.equals("..")) { // Go up to its parent
if (!stack.empty())
stack.pop();
} else if (!dir.equals(".")) { // Enter its subdirectory
stack.push(dir);
}
}
// No redundant "/"
}
// Construct simplified path
if (stack.empty()) // No subdirectory
return "/";
StringBuilder result = new StringBuilder();
for (String s : stack.toArray(new String[stack.size()]))
result.append("/"+s);
return result.toString();
}
}
Also refer to http://mounttop.blogspot.com/2014/03/leetcode-simplify-path.htmlhttp://stupidcodergoodluck.wordpress.com/2013/11/16/leetcode-simplify-path/
Read full article from LeetCode - Simplify Path | Darren's Blog
