Simplify Path

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

For example,

• path ="/home/", =>"/home"
• path ="/a/./b/../../c/", =>"/c"

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"..

图例

分析

首先熟悉一下Unix-style的路径构成规则：

中间是"."的情况直接去掉

是".."时删掉它上面挨着的一个路径

如果是空的话返回"/"

如果有多个"/"只保留一个

那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一处理即可

代码

// 时间复杂度O(n)，空间复杂度O(n)
class Solution {
    public String simplifyPath(String path) {
        // corner case
        if(path.length()<=1) return path;
        String[] each = path.split("/");
        Stack<String> stack = new Stack<>();

        for(String curr : each){
            if(curr.equals("..")){
                if(!stack.empty())  stack.pop();   // "a", "b", ".." ==> "a" because  .. go to partent directory    
            }else if(!curr.equals(".")  && curr.isEmpty()){
                stack.push(curr); // regular case 
            }
        }
        String result = "";
        if(stack.empty()) return"/";
        while(!stack.empty()){
            String newPop = stack.pop();
            result = "/" + newPop + result; // final result
        }

        return result;
    }
}