Unix Path Resolution Algorithm

Given a Unix path, represented as a list of strings, return its resolved version.

In Unix, “..” means to go to the previous directory and “.” means to stay on the current directory. By resolving, we mean to evaluate the two symbols so that we get the final directory we’re currently in.

Constraints
n ≤ 100,000 where n is the length of path
Example 1
Input
path = [“usr”, “..”, “usr”, “.”, “local”, “bin”, “docker”]
Output
[“usr”, “local”, “bin”, “docker”]
Explanation
The input represents “/usr/../usr/./local/bin” which resolves to “/usr/local/bin/docker”

Example 2
Input
path = [“bin”, “..”, “..”]
Output
[]
Explanation
The input represents “/bin/../..” which resolves to “/”

Unix Path Resolution by Simulation

We can simulate the process and pop the last directory when current stack/list is not empty. Ignore “.” as it doesn’t change directory. We can use a list i.e [] in Python to simulate the stack of directories.

1
2
3
4
5
6
7
8
9

class Solution:
    def unixPathResolution(self, path):
        ans = []
        for i in path:
            if i == ".." and len(ans) > 0:
                ans.pop()
            elif not (i in [".", ".."]):
                ans.append(i)
        return ans

class Solution:
    def unixPathResolution(self, path):
        ans = []
        for i in path:
            if i == ".." and len(ans) > 0:
                ans.pop()
            elif not (i in [".", ".."]):
                ans.append(i)
        return ans

Alternatively, we can use the deque and convert it to list.

1
2
3
4
5
6
7
8
9

class Solution:
    def unixPathResolution(self, path):
        ans = deque()
        for i in path:
            if i == ".." and len(ans) > 0:
                ans.pop()
            elif not (i in [".", ".."]):
                ans.append(i)
        return list(ans)

class Solution:
    def unixPathResolution(self, path):
        ans = deque()
        for i in path:
            if i == ".." and len(ans) > 0:
                ans.pop()
            elif not (i in [".", ".."]):
                ans.append(i)
        return list(ans)

The Unix Path Directory Resolution Implementation in C++:

1
2
3
4
5
6
7
8
9
10
11
12
13

vector<string> unixPathResolution(vector<string>& path) {
    vector<string> ans;
    for (auto &n: path) {
        if (n == "..") {
            if (!ans.empty()) {
                ans.pop_back();
            }            
        } else if (n != ".") {
            ans.push_back(n);
        }
    }
    return ans;
}

vector<string> unixPathResolution(vector<string>& path) {
    vector<string> ans;
    for (auto &n: path) {
        if (n == "..") {
            if (!ans.empty()) {
                ans.pop_back();
            }            
        } else if (n != ".") {
            ans.push_back(n);
        }
    }
    return ans;
}

See also: C++ Coding Exercise – How to Simplify Path?

–EOF (The Ultimate Computing & Technology Blog) —