We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Simplify Path

Number: 71

Difficulty: Medium

Paid? No

Companies: Meta, Capital One, Google, Oracle, Bloomberg, Amazon, Microsoft, Upstart, Patreon, Apple, Tinkoff, Yandex, Uber, TikTok, Coinbase

Problem Description

Given an absolute Unix-style file system path, simplify it to its canonical form. This involves handling multiple consecutive slashes, current directory symbols ('.'), and parent directory symbols ('..') correctly.

Key Insights

  • Use a stack to handle the directory names.
  • Ignore empty strings or '.' as they represent no change in the directory.
  • When encountering '..', pop the top of the stack if it's not empty.
  • All other valid strings are treated as directory names and pushed onto the stack.
  • Finally, join the elements in the stack with '/' and prepend a slash to form the canonical path.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the path string. Space Complexity: O(n) in the worst-case scenario where all directories are valid and stored in the stack.

Solution

We approach the problem by:

  1. Splitting the input path by the '/' delimiter.
  2. Iterating through the resulting tokens:
    • Skip tokens that are empty or equal to '.'.
    • When encountering '..', pop an element from the stack if it exists.
    • Otherwise, push the token onto the stack as a valid directory name.
  3. After processing all tokens, the stack contains the valid path components. We then construct the simplified path by concatenating these components with '/' in between, making sure it starts with a '/'.
  4. Edge cases include handling the root directory where the stack might be empty.

Code Solutions

def simplifyPath(path):
    # Split the path by '/'
    parts = path.split('/')
    # Initialize a stack to store valid directory names
    stack = []
    # Process each part from the split operation
    for part in parts:
        # Skip empty parts or the current directory symbol
        if not part or part == '.':
            continue
        # If encountering a parent directory symbol, pop if possible
        if part == '..':
            if stack:
                stack.pop()
        else:
            # Otherwise, push the valid directory name onto the stack
            stack.append(part)
    # Construct the canonical path by joining the stack with '/'
    return '/' + '/'.join(stack)

# Example usage
print(simplifyPath("/home//foo/"))
← Back to All Questions