Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

Solution:

维护一个栈，对于每一个块（以‘/’作为分界）进行分析，

如果遇到‘../’则表示要上一层，那么就是进行出栈操作，

如果遇到‘./’则是停留当前，直接跳过，其他文件路径则直接进栈即可。

最后根据栈中的内容转换成路径即可（这里是把栈转成数组，然后依次添加）。

时间上不会超过两次扫描（一次是进栈得到简化路径，一次是出栈获得最后结果），所以时间复杂度是O(n)，空间上是栈的大小，也是O(n)。

public class Solution {
    public String simplifyPath(String path) {
        if(path == null || path.length() == 0)
            return "";
        
        LinkedList stack = new LinkedList();
        StringBuilder res = new StringBuilder();
        int i = 0;
        
        while(i < path.length()) {
            int index = i;
            StringBuilder temp = new StringBuilder();
            
            //divide path by '/'
            while(i < path.length() && path.charAt(i) != '/') {
                temp.append(path.charAt(i));
                i++;
            }
            
            if(index != i) {
                String st = temp.toString();
                if(st.equals("..")) {
                    if(!stack.isEmpty())
                        stack.pop();
                }else if(!st.equals("."))
                    stack.push(st);
            }
            i++;
        }
        
        if(!stack.isEmpty()) {
            String[] s = stack.toArray(new String[stack.size()]);
            for(int j = s.length - 1; j >= 0; j--) {
                res.append("/" + s[j]);
            }
        }
        
        if(res.length() == 0)
            return "/";
        
        return res.toString();
    }
}