Problem description:

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

For example

1
2
3
4
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
path = "/a/../../b/../c//.//", => "/c"
path = "/a//b////c/d//././/..", => "/a/b/c"

In a UNIX-style file system, a period (‘.’) refers to the current directory, so it can be ignored in a simplified path. Additionally, a double period (“..”) moves up a directory, so it cancels out whatever the last directory was. For more information, look here: https://en.wikipedia.org/wiki/Path_(computing)#Unix_style

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:

The idea is to think of we need to keep the visited paths in a way that we could easily find the last one(need to go back one directory if we meet ..).
Then we can make the pushing to stack more strict, ie: only pushing the things we want into stack. So we don’t need to push . into stack.
Another thing to mention in python is the join, separator.join(iterable)

1
2
3
4
5
6
7
8
9
10
class Solution:
    def simplifyPath(self, path: str) -> str:
        stk = []
        for p in path.split('/'):
            if p == '..':
                if stk:
                    stk.pop()
            elif p and p != '.':
                stk.append(p)
        return '/'+'/'.join(stk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    string simplifyPath(string path) {
        string tmp;
        vector<string> stk;
        stringstream ss(path);
        
        while(getline(ss, tmp, '/')){ //use '/' as separator and get string from ss to tmp
            if(tmp == "" || tmp == ".") continue;
            if(tmp == ".." && !stk.empty()) stk.pop_back(); // ".." so remove last path in stack
            else if(tmp != "..") stk.push_back(tmp);
        }
        
        string res;
        for(auto str: stk) res+= "/"+str;
        return res.empty()? "/" : res;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$
reference: