Simplify Path medium

Problem Statement

Given a string representing a file system path, simplify it. A simplified path should not have redundant components (e.g., ./, ../) and should not have multiple slashes (//).

Example 1

Input: "/home//foo/" Output: "/home/foo" Explanation: The redundant slashes are removed.

Example 2

Input: "/a/./b/../../c/" Output: "/c" Explanation: ./ is removed, and ../ moves one level up.

Steps

1. Split the path: Split the input string into a list of components using the / character as a delimiter.
2. Initialize a stack: Use a stack to track the current path.
3. Iterate through components: Process each component:
   • If the component is empty or ".", ignore it.
   • If the component is "..":
     • If the stack is not empty, pop an element (move up one level).
     • Otherwise, ignore it (cannot move up from the root).
   • Otherwise (it's a regular directory name):
     • Push the component onto the stack.
4. Construct the simplified path: Join the elements in the stack with / and prepend a / if necessary.

Explanation

The algorithm uses a stack to efficiently manage the path traversal. The stack maintains the order of directories encountered while simplifying the path. The use of "." and ".." is handled appropriately to account for self-referencing and parent directory traversal. The final join operation reconstructs the simplified path.

Code

def simplifyPath(path):
    """
    Simplifies a file system path.

    Args:
        path: The input file system path (string).

    Returns:
        The simplified path (string).
    """
    stack = []
    components = path.split('/')

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

    simplified_path = '/' + '/'.join(stack)
    return simplified_path

Complexity

• Time Complexity: O(N), where N is the length of the input string. This is because we iterate through the string components once.
• Space Complexity: O(N) in the worst case, where the stack can potentially store all components of the input path (e.g., "/a/b/c/d"). In the best case (a path with few or no components requiring stacking), the space complexity would be O(1).