LeetCode 71: Simplify Path Solution in Python Explained

Problem Statement

LeetCode 71, Simplify Path, is a medium-level problem where you’re given a string path representing an absolute Unix-style file path. Your task is to simplify it into its canonical form and return it as a string. The canonical path:

Starts with a single slash /.
Has no redundant slashes (e.g., // becomes /).
Does not end with a slash unless it’s the root (/).
Resolves special components:

. (current directory, stays in place).
.. (parent directory, go up one level).
Empty or single slash (ignored).

Constraints

1 <= path.length <= 3000: Path length is between 1 and 3000.
path consists of English letters, digits, period '.', slash '/', or '_'.
path is a valid absolute Unix path (starts with '/').

Example

Input: path = "/home/"
Output: "/home"
Explanation: Trailing slash removed.

Input: path = "/home//foo/"
Output: "/home/foo"
Explanation: Double slashes become single, trailing slash removed.

Input: path = "/home/user/Documents/../Desktop"
Output: "/home/user/Desktop"
Explanation: ".." moves up from Documents to user, simplifies to "/home/user/Desktop".

Input: path = "/../"
Output: "/"
Explanation: ".." from root stays at root.

Understanding the Problem

How do you solve LeetCode 71: Simplify Path in Python? For path = "/home//foo/", simplify it to "/home/foo" by removing redundant slashes and handling special components. We need to parse the path, interpret . and .., and build the canonical path. We’ll explore two approaches: a Stack-Based Parsing Solution (optimal and primary) and an Alternative with String Splitting (simpler but similar). The stack method runs in O(n) time with O(n) space, efficiently handling path components.

Solution 1: Stack-Based Parsing Approach (Primary)

Explanation

Use a stack to build the canonical path by processing components between slashes. Split the path on '/', then for each component:

Ignore empty strings, single dots, or leading/trailing slashes.
For ".." pop the stack (go up), if not empty.
For valid names, push onto the stack.

Finally, construct the path from the stack, starting with a single '/'.

Here’s a flow for "/home//foo/":

Split: ["", "home", "", "foo", ""]
Stack: [] -> ["home"] -> ["home", "foo"]
Build: "/" + "home" + "/" + "foo" = "/home/foo"

Split Path.

Use '/' as delimiter.

Process Components.

Handle '.', '..', and valid names with stack.

Build Canonical Path.

Join stack with '/' and prepend '/'.

Return Result.

Step-by-Step Example

Example 1: path = "/home//foo/"

We need "/home/foo".

Goal: Simplify path to canonical form.
Result for Reference: "/home/foo".
Start: path = "/home//foo/", stack = [].
Step 1: Split path.

components = ["", "home", "", "foo", ""].

Step 2: Process components.

"" (empty) -> skip.
"home" -> stack = ["home"].
"" -> skip.
"foo" -> stack = ["home", "foo"].
"" -> skip.

Step 3: Build path.

stack = ["home", "foo"], result = "/" + "home" + "/" + "foo" = "/home/foo".

Finish: Return "/home/foo".

Example 2: path = "/home/user/Documents/../Desktop"

We need "/home/user/Desktop".

Start: stack = [].
Step 1: Split.

components = ["", "home", "user", "Documents", "..", "Desktop"].

Step 2: Process.

"" -> skip.
"home" -> stack = ["home"].
"user" -> stack = ["home", "user"].
"Documents" -> stack = ["home", "user", "Documents"].
".." -> pop, stack = ["home", "user"].
"Desktop" -> stack = ["home", "user", "Desktop"].

Step 3: Build.

result = "/" + "home" + "/" + "user" + "/" + "Desktop" = "/home/user/Desktop".

Finish: Return "/home/user/Desktop".

How the Code Works (Stack-Based Parsing)

Here’s the Python code with line-by-line explanation:

def simplifyPath(path: str) -> str:
    # Line 1: Split path into components
    components = path.split('/')

    # Line 2: Initialize stack
    stack = []

    # Line 3: Process each component
    for comp in components:
        if comp == '' or comp == '.':  # Ignore empty or current dir
            continue
        elif comp == '..':  # Go up one level
            if stack:
                stack.pop()
        else:  # Valid directory/file name
            stack.append(comp)

    # Line 4: Build canonical path
    if not stack:
        return "/"
    result = "/" + "/".join(stack)

    # Line 5: Return simplified path
    return result

Alternative: String Splitting Approach

Explanation

Split the path into components and process them similarly, but use a list comprehension or filter to clean components upfront, then build the path. This is less dynamic than the stack but achieves the same result with a different structure.

Clean Components.

Filter out invalid parts.

Process Path.

Build path, handling ".." by tracking position.

Return Result.

Step-by-Step Example (Alternative)

For "/home//foo/":

Start: path = "/home//foo/".
Step 1: Split and clean.

components = ["", "home", "", "foo", ""] -> ["home", "foo"].

Step 2: Build.

result = "/" + "home" + "/" + "foo" = "/home/foo".

Finish: Return "/home/foo".

How the Code Works (String Splitting)

def simplifyPathSplit(path: str) -> str:
    # Line 1: Split and filter components
    components = [comp for comp in path.split('/') if comp and comp != '.']

    # Line 2: Initialize result list
    result = []

    # Line 3: Process components
    for comp in components:
        if comp == '..':
            if result:
                result.pop()
        else:
            result.append(comp)

    # Line 4: Build canonical path
    return "/" + "/".join(result) if result else "/"

Complexity

Stack-Based Parsing:

Time: O(n) – Single pass through string, splitting and processing.
Space: O(n) – Stack stores components.

String Splitting:

Time: O(n) – Splitting and processing.
Space: O(n) – Result list.

Efficiency Notes

Stack-Based Parsing is O(n) time and O(n) space, optimal for LeetCode 71 as it processes the path dynamically. String Splitting is also O(n) time and O(n) space, slightly more upfront work with filtering but equally effective.

Key Insights

Tips to master LeetCode 71:

Stack Power: Use stack to handle directory hierarchy.
Component Rules: Skip '.', pop for '..', push valid names.
Root Case: Return "/" for empty or root paths.

Additional Example

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

Goal: "/c".
Stack: ["a", "b"] -> ["a"] -> [] -> ["c"] -> "/c".
Result: "/c".

Edge Cases

Root: "/" – Return "/".
Multiple Slashes: "///" – Return "/".
Only Dots: "/././" – Return "/".

Final Thoughts

The Stack-Based Parsing solution is a top pick for LeetCode 71 in Python—flexible, efficient, and perfect for path simplification. For a related challenge, try LeetCode 70: Climbing Stairs to switch to DP! Ready to simplify? Solve LeetCode 71 on LeetCode now and test it with "/home//foo/" or "/a/./b/../../c/" to master path handling. Dive in and streamline those paths!