algoadvance

Given a string path, which is an absolute path (starting with a slash ‘/’) to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period ‘.’ refers to the current directory, a double period ‘..’ refers to the directory up a level, and any multiple consecutive slashes (i.e., ‘//’) are treated as a single slash ‘/’. For this problem, any other format of periods such as ‘…’ are treated as file/directory names.

The canonical path should:

  1. Always begin with a slash ‘/’.
  2. Eliminate multiple slashes.
  3. Eliminate any period ‘.’ that describes the current directory.
  4. Eliminate any consecutive periods ‘..’ that move up a directory.
  5. Return the simplified canonical path.

Clarifying Questions

  1. Should the function return the root path ‘/’ if the input path leads to an empty string after simplification?
    • Yes, the function should return ‘/’ in such cases.
  2. Are there always valid and well-formed path strings provided as input?
    • Yes, the input path is assumed to be a valid and well-formed absolute path.
  3. Is the input path case-sensitive?
    • Yes, Unix-style paths are typically case-sensitive.

Strategy

  1. Split the input path by slashes to get the components.
  2. Use a stack to process each component:
    • If the component is empty or a single period ‘.’, skip it.
    • If the component is a double period ‘..’, pop from the stack if the stack is not empty.
    • Otherwise, push the component to the stack.
  3. Join the components in the stack with a slash ‘/’ and ensure the result starts with a slash.

Code

def simplifyPath(path: str) -> str:
    # Split the path by '/'
    components = path.split('/')
    stack = []

    for component in components:
        if component == '' or component == '.':
            continue
        elif component == '..':
            if stack:
                stack.pop()
        else:
            stack.append(component)

    # Join the stack to form a canonical path
    return '/' + '/'.join(stack)

# Test examples
print(simplifyPath("/home/"))        # Output: "/home"
print(simplifyPath("/../"))          # Output: "/"
print(simplifyPath("/home//foo/"))   # Output: "/home/foo"
print(simplifyPath("/a/./b/../../c/")) # Output: "/c"

Time Complexity

The given solution has a time complexity of O(N), where N is the length of the input path string. This is because:

  1. Splitting the path string costs O(N).
  2. Traversing each component and performing constant-time operations (push, pop) on the stack also costs O(N).

Thus, the overall time complexity is O(N).

Try our interview co-pilot at AlgoAdvance.com