Simplify a Unix Path
Problem
Given an absolute Unix-style path, return its simplest equivalent form. In the input, . means the current directory, .. means the parent directory (the parent of the root is the root), and several slashes in a row count as one. Any other name, including ..., is an ordinary directory. The result must start with a single slash, separate names with single slashes and not end with a slash unless it is the root itself.
Examples
Input: path = "/a/./b/../../c/"
Output: "/c"
Why: enter a, stay, enter b, leave b, leave a, enter cInput: path = "/home//user/.../docs/"
Output: "/home/user/.../docs"
Why: the double slash collapses, and three dots is just a directory nameInput: path = "/../"
Output: "/"
Why: edge case, going up from the root stays at the rootHints
0 / 3
Split the path on '/'. Empty pieces come from repeated or trailing slashes and can be ignored, and so can '.'.
Walking the pieces in order, a name goes one directory deeper and '..' undoes the most recent name. Undoing the most recent thing first is what a stack does.
Push names, pop on '..' only when the stack is not empty, and at the end join the stack with '/' and put a single '/' in front.
Solution
The directories you are inside form a stack: entering a directory pushes its name and .. pops the last one entered. Splitting on / turns runs of slashes and a trailing slash into empty pieces, which are skipped along with ., so the only real cases left are a name and ... Popping only when the stack is not empty is the rule that the root's parent is the root. Whatever remains on the stack, bottom to top, is the path from the root, and joining it with a leading slash gives the canonical form, including / for an empty stack. Time and space are O(n) in the length of the path.
def simplify_path(path):
stack = [] # directories entered, deepest on top
for part in path.split("/"):
if part == "..":
if stack: # the parent of the root is the root
stack.pop()
elif part and part != ".": # skip empty pieces and "."
stack.append(part)
return "/" + "/".join(stack)
print(simplify_path("/a/./b/../../c/")) # -> /c
print(simplify_path("/home//user/.../docs/")) # -> /home/user/.../docs
print(simplify_path("/../")) # -> /Stuck on the idea rather than the code? Stack Basics covers it.