Domain 2MediumCORE

Simplify Path

We are given an absolute Unix-style file path string path. Our goal is to normalize this into a canonical form based on specific rules: single slashes separate directories, multiple consecutive slashes count as one, current directory references (.) are ignored, and parent directory references (..) move us up the hierarchy. The output must start with /, have no trailing slash, and contain only valid directory names (no . or ..).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#String#Stack

71. Simplify Path

Model: qwen3.5:9b
Topics: String,Stack
FAANG asked: 1
Acceptance rate: 34.9%


Problem Breakdown

We are given an absolute Unix-style file path string path. Our goal is to normalize this into a canonical form based on specific rules: single slashes separate directories, multiple consecutive slashes count as one, current directory references (.) are ignored, and parent directory references (..) move us up the hierarchy. The output must start with /, have no trailing slash, and contain only valid directory names (no . or ..).

Inputs: A string path starting with '/'. Length between 1 and 3000 characters. Outputs: A normalized path string adhering to canonical rules. Implicit Constraints/Edge Cases:

  • Handling the root level (/) where we cannot go above it (ignoring extra ..).
  • Multiple slashes like // or leading/trailing slashes which need collapsing/removal.
  • Empty directory names resulting from consecutive slashes must be skipped during parsing.

Intuition

If I were to approach this naively, I might try using string replacement methods—replacing multiple / with a single one and removing specific substrings like /.. However, that fails immediately because the logic depends on state: specifically, how deep we are in the directory tree. Replacing strings doesn’t track whether an operation should push us deeper or pop us up.

The core insight is recognizing this as a stack-based problem. A file path represents a sequence of directories from root to target.

  1. We can split the string by / to get individual components (directories).
  2. Each component tells us what action to take:
    • Ignore empty strings (from multiple slashes or leading/trailing slash).
    • If we see ., it means “stay here,” so do nothing.
    • If we see .., it means “go up one level.” This corresponds to popping the last directory from our stack, provided we aren’t already at root.
    • Any other string is a valid subdirectory name; push onto the stack.

By processing components sequentially and maintaining a list of directories in memory (acting as a stack), we can reconstruct the clean path at the end without worrying about complex regex patterns or state errors during traversal.

Approach

  1. Initialize an empty list stack to hold directory names.
  2. Split the input string by /. This naturally handles multiple slashes because they produce empty strings between them, which we will ignore.
  3. Iterate through each component from the split:
    • Skip if it is an empty string (handles leading/trailing/multiple slashes).
    • If it equals ., skip (current directory does not change path).
    • If it equals ..: check if stack has elements. If yes, pop one element (move up). If no, we are at root and stay there.
    • Otherwise: append the component to the list.
  4. Join the items in the list with / as a separator. Prepend or ensure the result starts with /. Since join doesn’t add leading slashes, simply return '/' + '/'.join(stack).

Complexity Analysis

  • Time Complexity: O(N), where N is the length of path. We iterate through the string once to split it and then process each component exactly once. String splitting takes linear time relative to input size.
  • Space Complexity: O(K), where K is the number of directory components in the canonical path (worst case, roughly proportional to N). This accounts for the stack/list storage required to build the result string.

Solution

def simplifyPath(path: str) -> str:
    # Split by '/' creates a list of directories and empty strings 
    # between multiple slashes or at boundaries.
    components = path.split('/')
    
    stack = []
    
    for component in components:
        if not component:
            continue
        
        elif component == '.':
            continue
            
        elif component == '..':
            if stack:
                stack.pop()
        
        else:
            # Valid directory name, push to stack
            stack.append(component)
            
    return '/' + '/'.join(stack)

Edge Cases Handled

  • Root only (/ or /../): The loop processes components. If .. is encountered at root (stack empty), the condition if stack: prevents popping, keeping us at root. Result becomes just /.
  • Multiple slashes (//, ///): Splitting creates empty strings between them; these are skipped by if not component: continue.
  • Trailing slash: The split handles this naturally (creates an empty string at the end), which is ignored, ensuring no trailing slash in output.
  • Current directory dots (.): Explicitly checked and skipped to maintain current depth without adding a name.