Problem Statement in English

You’re given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system. Convert it to the simplified canonical path.

Approach

We can handle the input string by stripping the trailing slashes and splitting the string by the / character. We can then iterate through the resulting list of components and use a stack to build the simplified path.

If we encounter a .., we pop the last element from the stack (if it exists). If we encounter a ., we do nothing. If we encounter an empty string (which can happen due to consecutive slashes), we also do nothing. For any other valid directory name, we push it onto the stack.

Finally, we join the elements in the stack with / and prepend a leading / to form the canonical path.

And we’re done!

Solution in Python


class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []

        for p in path.rstrip("/").split("/"):
            if p == "..":
                if stack:
                    stack.pop()
            elif p == "." or p == "":
                continue
            else:
                stack.append(p)

        return "/" + "/".join(stack)

Complexity

  • Time: $O(n)$
    Since we are iterating through the string path once, the time complexity is linear with respect to the length of the input string.

  • Space: $O(n)$
    Since we are using a stack to store the components of the simplified path, the space complexity is also linear with respect to the length of the input string.

And we are done.