Description

LeetCode 71

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

Analysis

Initially, I did’t understand the intent of the problem. So I was confused.

Actually, the problem is to describe the path in unix system. “.” means that the path does not change. “..” means the path changes to its parent. If we understand the intent, we can easily come up with the stack method.

First split the path with regular expression “/+”. Then push the path to the stack. When we meet “..”, pop the stack. Finally, pop the stack and return the result.

The time and space are both \(O(n)\).

Solution

class Solution {
    public String simplifyPath(String path) {
        Stack<String> s=new Stack<>();
        String[] paths=path.split("/+");
        String res="";
        for(String str:paths)
        {
            if(str.equals(".."))
            {
                if(s.size()>0)
                {
                    s.pop();
                }
            }
            else if(!str.equals(".")&&!str.equals(""))
            {
                s.push(str);
            }
        }
        while(s.size()>0)
        {
            res="/"+s.pop()+res;
        }
        if(res.length()==0)
            res="/";
        return res;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/SimplifyPath.java

Leave a Reply

Your email address will not be published. Required fields are marked *