LeetCode 71: Simplify Path

Problem Restatement

We are given a Unix-style absolute file path.

We need to simplify it into its canonical form.

The rules are:

1. A single dot "." means the current directory.
2. A double dot ".." means move to the parent directory.
3. Multiple consecutive slashes should be treated as a single slash.
4. Any other name should be treated as a normal directory name.
5. The result must:
   • Start with a single slash
   • Have exactly one slash between directories
   • Not end with a trailing slash unless the path is just "/"

The official constraints are 1 <= path.length <= 3000, and the path contains English letters, digits, ., _, and /. (leetcode.com)

Input and Output

Function shape:

def simplifyPath(path: str) -> str:
    ...

Examples

For:

path = "/home/"

The trailing slash should be removed.

The answer is:

"/home"

For:

path = "/../"

Moving above the root directory is impossible.

So the path remains:

"/"

For:

path = "/home//foo/"

Multiple slashes collapse into one slash.

The answer is:

"/home/foo"

For:

path = "/a/./b/../../c/"

Step by step:

/a
/a/b
/a
/
/c

So the answer is:

"/c"

First Thought: Process One Directory at a Time

Unix paths are naturally separated by slashes.

For example:

"/a/./b/../../c/"

splits into:

["", "a", ".", "b", "..", "..", "c", ""]

The empty strings come from leading, trailing, or repeated slashes.

We can process each component one by one.

Key Insight

A stack perfectly matches directory navigation.

The stack always represents the current path from root.

For example:

"/a/./b/../../c/"

Processing step by step:

Finally:

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

gives:

"/c"

Algorithm

Split the path by slash:

parts = path.split("/")

Create an empty stack.

For each part:

1. Ignore empty strings and "."
2. If the part is "..":
   • Pop from the stack if the stack is not empty
3. Otherwise:
   • Push the directory name onto the stack

Finally return:

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

Correctness

The stack always stores the canonical directory sequence from the root to the current directory.

When the algorithm sees a normal directory name, entering that directory appends it to the current path, so pushing it onto the stack is correct.

When the algorithm sees ".", the current directory does not change, so ignoring it is correct.

When the algorithm sees "..", the path should move to the parent directory. Removing the top directory from the stack performs exactly this operation. If the stack is empty, the path is already at the root, so moving higher has no effect.

Empty components produced by repeated or leading slashes do not represent real directories, so ignoring them is correct.

After all components are processed, joining the stack with single slashes reconstructs the canonical absolute path.

Complexity

Implementation

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

        for part in path.split("/"):
            if part == "" or part == ".":
                continue

            if part == "..":
                if stack:
                    stack.pop()

            else:
                stack.append(part)

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

Code Explanation

Create a stack to store directory names:

stack = []

Split the path into components:

for part in path.split("/"):

Ignore empty strings and ".":

if part == "" or part == ".":
    continue

Handle parent directory:

if part == "..":
    if stack:
        stack.pop()

If the stack is already empty, we stay at root.

Otherwise, the component is a real directory:

else:
    stack.append(part)

Finally rebuild the canonical path:

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

Testing

def run_tests():
    s = Solution()

    assert s.simplifyPath("/home/") == "/home"

    assert s.simplifyPath("/../") == "/"

    assert s.simplifyPath("/home//foo/") == "/home/foo"

    assert s.simplifyPath("/a/./b/../../c/") == "/c"

    assert s.simplifyPath("/") == "/"

    assert s.simplifyPath("/.../a/../b/c/../d/./") == "/.../b/d"

    assert s.simplifyPath("/a//b////c/d//././/..") == "/a/b/c"

    print("all tests passed")

run_tests()