Simplify Path

71.Simplify Path

String

Stack

Problem Statement:

Given a string path, which is an absolute Unix-style path (starting with a slash /), simplify it. The path may contain extra slashes /, . (current directory), or .. (parent directory). Return the simplified canonical path.

Example:

Input:

"/a/./b/../../c/"

→

Output:

"/c"

The input path simplifies to the canonical path /c.

Algorithm:

1. Split the input path into components using / as the delimiter.
2. Iterate through the components:
   • Skip empty strings and . (current directory).
   • If .. is found, pop from the stack unless it's empty.
   • Push valid directory names onto the stack.
3. Join the stack elements with / to construct the canonical path.

public String simplifyPath(String path) {
    // Stack to track valid directories
    Stack<String> stack = new Stack<>();

    // Split the path into components
    String[] dirs = path.split("/"); 
    
    // Iterate through each directory
    for (String dir : dirs) { 
        // Skip "." and empty strings
        if (dir.equals(".") || dir.isEmpty()) { 
            continue;
        } else if (dir.equals("..")) {
            // Pop from stack for ".." if not empty
            if (!stack.isEmpty())  
                stack.pop();
        } else { 
            // Push valid directory to stack
            stack.push(dir);
        }
    }
    // Join stack elements to form the canonical path
    return "/" + String.join("/", stack); 
}

Complexity:

Time: O(n) | Space: O(n)