71.Simplify Path

Posted on | In

Stack, Medium

Question

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

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public String simplifyPath(String path) {
        // notice "", ".", "..", "/"
        Stack<String> stack = new Stack<>();
        StringBuffer res = new StringBuffer();
        String[] strArray = path.split("/");
        for(String str:strArray){
            if(str.equals("..")&&!stack.isEmpty())
                stack.pop();
            if(str.equals(".")||str.equals("")||str.equals(".."))     
                continue;
            else
                stack.push(str);
        }     
        for(String s:stack){
            res.append("/");
            res.append(s);
        }
        // corner case: "/../" return "/", so need to judge, in this case, String res is empty
        return res.toString().isEmpty()?"/":res.toString();
    }
}

Running time: O(n)

Space: O(n)