algoadvance

Leetcode 71. Simplify Path

Problem Statement:

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 have the following format:

1. The path starts with a single slash ‘/’.
2. Any two directories are separated by a single slash ‘/’.
3. The path does not end with a trailing ‘/’.
4. The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period ‘..’ or ‘.’ in the path).

Return the simplified canonical path.

Example:

1. Input: path = “/home/” Output: “/home”

2. Input: path = “/../” Output: “/”

3. Input: path = “/home//foo/” Output: “/home/foo”

Clarifying Questions:

1. Q: Can the input path start with characters other than / (like relative paths)?
   • A: No, the input path is always given as an absolute path.
2. Q: Should we handle symbolic links or just focus on the given rules?
   • A: Just focus on the given rules. We don’t handle symbolic links.

Strategy:

1. Split the Path: Split the given path based on the ‘/’ separator.
2. Initialize a Stack: Use a stack to track directories.
3. Process Each Component:
   • Skip empty components and ‘.’ (current directory).
   • If encountering ‘..’, pop the stack if it is not empty (move one directory up).
   • Push normal directory names onto the stack.
4. Reconstruct the Canonical Path: Join the components in the stack with ‘/’ to form the canonical path, ensuring it starts with a ‘/’.

Code:

import java.util.*;

public class SimplifyPath {
    public String simplifyPath(String path) {
        // Split the path by '/'
        String[] components = path.split("/");
        Stack<String> stack = new Stack<>();
        
        for (String component : components) {
            if (component.equals("") || component.equals(".")) {
                // Skip empty and current directory components
                continue;
            } 
            if (component.equals("..")) {
                // Move one directory up - Remove one directory if possible
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                // Add current directory name to the stack
                stack.push(component);
            }
        }
        
        // Reconstruct the canonical path
        StringBuilder result = new StringBuilder();
        for (String dir : stack) {
            result.append("/").append(dir);
        }
        
        // Return the canonical path, return "/" if it's empty
        return result.length() > 0 ? result.toString() : "/";
    }

    public static void main(String[] args) {
        SimplifyPath simplifier = new SimplifyPath();
        System.out.println(simplifier.simplifyPath("/home/")); // Output: "/home"
        System.out.println(simplifier.simplifyPath("/../")); // Output: "/"
        System.out.println(simplifier.simplifyPath("/home//foo/")); // Output: "/home/foo"
    }
}

Time Complexity:

• Time Complexity: O(n), where n is the length of the input string. We process each character of the input string exactly once.
• Space Complexity: O(n), because in the worst case, all components could be valid directory names, and we store them in the stack.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?