Leetcode 71. Simplify Path

This problem is asking us to simulate navigating through a Unix file system and return the final canonical path. We need to handle several special cases:

1. Directory Navigation: Normal directory names just extend our current path
2. Current Directory ('.'): These should be ignored as they don't change our location
3. Parent Directory ('..'): These move us up one level in the hierarchy
4. Multiple Slashes: Should be treated as single separators
5. Trailing Slashes: Should be removed unless we're at root

The key insight is that we're essentially simulating a stack-based navigation system where we build up our path and occasionally need to backtrack.

The most straightforward approach would be to repeatedly scan the entire path string and apply transformations until no more changes can be made.

We could iteratively:

1. Replace all consecutive slashes with single slashes using string replacement
2. Find each occurrence of '/.' and remove it (since it refers to current directory)
3. Find each occurrence of '/..' and remove it along with the preceding directory
4. Remove trailing slashes

This would require multiple passes through the string, and for each '..' we encounter, we'd need to scan backwards to find the previous directory to remove. In the worst case with many '..' operations, we might need to scan the entire string multiple times, leading to poor performance on deeply nested paths with many parent directory references.

def simplifyPath(path):
    while True:
        changed = False
        import re
        new_path = re.sub(r'/+', '/', path)
        if new_path != path:
            path = new_path
            changed = True
        new_path = path.replace('/.', '')
        if new_path != path:
            path = new_path
            changed = True
        dot_dot_index = path.find('/..')
        if dot_dot_index != -1:
            if dot_dot_index == 0:
                path = path[3:]
            else:
                prev_slash = path.rfind('/', 0, dot_dot_index)
                if prev_slash == -1:
                    prev_slash = 0
                path = path[:prev_slash] + path[dot_dot_index + 3:]
            changed = True
        if not changed:
            break
    if not path.startswith('/'):
        path = '/' + path
    if len(path) > 1 and path.endswith('/'):
        path = path[:-1]
    return path if path else '/'

The breakthrough insight is recognizing that file system navigation is fundamentally a stack operation. Every time we enter a directory, we're 'pushing' onto our path stack. Every time we use '..', we're 'popping' from our path stack. This transforms a complex string manipulation problem into a simple stack simulation.

After seeing the brute force limitations of multiple string scans, a stack becomes the perfect data structure because:

Natural Hierarchy Modeling: File systems are inherently hierarchical - directories contain subdirectories, and we navigate deeper or back up. A stack's LIFO (Last In, First Out) property perfectly mirrors this - the most recently entered directory is the first one we exit when going up.

Efficient Backtracking: When we encounter '..', we need to go back to the parent directory. With a stack, this is just a pop() operation - O(1) time. With string manipulation, we'd need to find and remove the last directory, which requires scanning.

Clean State Management: The stack maintains our current path state naturally. Each directory we enter gets pushed, each '..' pops the most recent entry, and '.' operations are simply ignored.

Now that we understand why a stack is perfect for tracking our directory hierarchy, here's how we implement it:

1. Split and Filter: Split the path by '/' and filter out empty strings (from consecutive slashes) and '.' (current directory references)

2. Stack Processing: For each remaining component:

   • If it's '..': pop from stack (if not empty) to go up one directory
   • Otherwise: push the directory name onto the stack

3. Reconstruction: Join all stack elements with '/' and prepend with '/' for the root

The stack naturally handles the hierarchical nature of file systems - we build up the path as we go deeper, and '..' operations simply pop the most recent directory. This eliminates the need for multiple string scans and complex string manipulations.

def simplifyPath(path):
    stack = []
    components = path.split('/')
    
    for component in components:
        if component == '' or component == '.':
            continue
        elif component == '..':
            if stack:
                stack.pop()
        else:
            stack.append(component)
    
    return '/' + '/'.join(stack)

• Stack for path navigation: Use a stack whenever you need to process hierarchical paths or nested structures where you might need to "go back" - the stack naturally handles the parent directory (`..`) operations by popping the last directory, mimicking how file systems work.
• String splitting preprocessing: Split the path by `/` delimiter first, then process each component separately - this eliminates the complexity of handling multiple consecutive slashes and makes the logic focus purely on directory navigation rules.
• Component-based validation: Treat each path component individually: ignore empty strings and `.`, pop from stack for `..`, and push everything else - this separation makes the algorithm robust and handles edge cases like `...` (valid directory name) vs `..` (parent reference).
• Root directory boundary protection: Always check if the stack is empty before popping for `..` operations - attempting to go above root directory should be ignored, not cause errors, which prevents stack underflow and matches Unix filesystem behavior.
• Efficient path reconstruction: Join the final stack contents with `/` and prepend a single `/` rather than building the string incrementally - this avoids repeated string concatenation overhead and naturally handles the empty stack case (root directory only).
• Canonical form normalization: This tokenize-process-rebuild pattern applies broadly to parsing problems: configuration files, URL normalization, import path resolution - anywhere you need to simplify a hierarchical or nested input according to specific rules.