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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Simplify Path

Difficulty: Medium

Problem Description

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplified canonical path. The rules of a Unix-style file system include representations for the current directory ('.'), the parent directory ('..'), and handling multiple consecutive slashes as a single slash. The simplified canonical path must follow specific formatting rules.

Key Insights

  • A single period '.' represents the current directory and can be ignored.
  • A double period '..' moves up to the parent directory and should remove the last directory from the path if it exists.
  • Multiple consecutive slashes should be treated as a single slash.
  • Valid directory or file names may contain periods but should not be interpreted as current or parent directory indicators.
  • The final path must start with a single slash and should not end with a slash unless it is the root directory.

Space and Time Complexity

Time Complexity: O(n) - where n is the length of the input path, as we traverse the path once. Space Complexity: O(n) - for storing the result in a stack, in the worst case where the path has no '..' or '.'.

Solution

To solve the problem, we can use a stack data structure to keep track of the directories. We will split the input path by slashes to process each component. For each component:

  • If it is a valid directory name (not empty, '.' or '..'), we push it onto the stack.
  • If it is '..', we pop the last directory from the stack if it exists. After processing all components, we join the elements in the stack to form the simplified canonical path. Finally, we ensure to prepend a single slash.

Code Solutions

def simplifyPath(path: str) -> str:
    # Split the path into components based on the slash
    components = path.split('/')
    stack = []
    
    for component in components:
        if component == '' or component == '.':
            # Ignore empty components and current directory
            continue
        elif component == '..':
            # Go to the parent directory if possible
            if stack:
                stack.pop()
        else:
            # Valid directory name, push onto the stack
            stack.append(component)
    
    # Join all components in the stack to form the simplified path
    return '/' + '/'.join(stack)  # Ensure it starts with a slash
← Back to All Questions