Simplify Path medium

Problem Statement

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

In a Unix-like file system, a period '.' refers to the current directory, a double period '..' refers to the parent directory, and multiple slashes '/' are treated as a single slash. For example, /home//foo//bar/./baz represents the same location as /home/foo/bar/baz.

The simplified canonical path should have no redundant '.' or '..' sequences. If the path leads to the root directory, the result should be '/'.

Example 1

Input: path = "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name.

Example 2

Input: path = "/../" Output: "/" Explanation: Going one level up from the root directory is just the root directory.

Example 3

Input: path = "/home//foo/../bar//baz/./" Output: "/home/bar/baz"

Steps

1. Split the path: Split the input path string into an array of path segments using the '/' character as a delimiter. Ignore empty segments.

2. Iterate and Simplify: Iterate through the path segments. Maintain a stack to track the current path.

   • If a segment is ".", ignore it.
   • If a segment is "..", pop the top element from the stack (if the stack is not empty). This simulates moving up a directory level.
   • If a segment is neither "." nor "..", push it onto the stack.

3. Construct the Result: After iterating through all segments, join the elements in the stack with '/' characters. If the stack is empty, the simplified path is '/'.

Explanation

The stack acts as a way to efficiently track the path. Pushing represents moving down into a directory, and popping represents moving up. The use of a stack ensures that we handle the order of directory traversal correctly. Ignoring "." and appropriately handling ".." guarantees the removal of redundant elements and a simplified path.

Code

function simplifyPath(path: string): string {
    const segments = path.split('/').filter(segment => segment !== '');
    const stack: string[] = [];

    for (const segment of segments) {
        if (segment === '.') {
            continue; // Ignore '.'
        } else if (segment === '..') {
            if (stack.length > 0) {
                stack.pop(); // Move up a directory
            }
        } else {
            stack.push(segment); // Add directory to path
        }
    }

    if (stack.length === 0) {
        return '/'; // Root directory
    } else {
        return '/' + stack.join('/'); //Reconstruct the simplified path
    }
}

Complexity

• Time Complexity: O(N), where N is the number of path segments in the input string. We iterate through the segments once.
• Space Complexity: O(N) in the worst case, to store the stack of path segments. The space used is proportional to the number of path segments (the stack size). In the best case, if the path is already simplified, it's O(1).