Simplifying UNIX Paths: A Dive into LeetCode Problem 71

Let’s look into another interesting coding interview question to realize that using right data structure makes it easier to solve a problem at hand.

Problem Statement

Given a UNIX-style path (string), we need to simplify it. For those new to UNIX, a path is a way to represent the location of a file or folder. In this problem, the following rules apply:

• .. means moving up a directory.
• . means staying in the current directory.
• Multiple slashes // can be replaced by a single /.

Example:

Input: "/home//foo/"

Output: "/home/foo"

1. Brute Force Solution

A naive approach would be to use string manipulation functions repeatedly until no further simplifications can be made. This means:

1. Replacing all // with /.
2. Handling all instances of /./ by replacing with /.
3. Tackling all the /../ by removing the preceding directory.

This iterative process will continue until no more changes are detected in the path string.

Java Code for Brute Force Solution:

public String simplifyPath(String path) {

    while (path.indexOf("//") != -1) {
        path = path.replace("//", "/");
    }

    while (path.indexOf("/./") != -1) {
        path = path.replace("/./", "/");
    }

    int i;
    while ((i = path.indexOf("/../")) != -1) {
        int start = path.lastIndexOf('/', i - 1);
        if (start == -1) {
            path = path.substring(i + 3);
        } else {
            path = path.substring(0, start) + path.substring(i + 3);
        }
    }

    if (path.endsWith("/..")) {
        int start = path.lastIndexOf('/', path.length() - 4);
        if (start == -1) {
            path = "/";
        } else {
            path = path.substring(0, start + 1);
        }
    }
    
    if (path.equals("/.")) {
        path = "/";
    }

    if (path.endsWith("/.")) {
        path = path.substring(0, path.length() - 2);
    }

    if (path.length() > 1 && path.endsWith("/")) {
        path = path.substring(0, path.length() - 1);
    }

    return path;
}

Time Complexity: Potentially O(n²) in the worst case because of repeated string replacements.

Space Complexity: O(n) for storing the modified string.

2. Optimal Solution

The idea is to split the path by / and use a stack to keep track of the directories. When we see a .., we pop an element (directory) off the stack, and when we see a directory name, we push it onto the stack.

Java Code for Optimal Solution:

public String simplifyPath(String path) {
    // Split the path based on /
    String[] parts = path.split("/");
    Stack<String> stack = new Stack<>();

    for (String part : parts) {
        // If "..", pop a directory from stack
        if ("..".equals(part)) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } 
        // If it's not "." or empty, it's a directory, so push to stack
        else if (!".".equals(part) && !part.isEmpty()) {
            stack.push(part);
        }
    }

    StringBuilder result = new StringBuilder();
    // Construct the result from the stack
    for (String dir : stack) {
        result.append("/").append(dir);
    }
    
    // If stack is empty, return root
    return result.length() == 0 ? "/" : result.toString();
}

🔍 Illustration:

Given path = "/a/./b/../../c/"

• Split on / gives: ["", "a", ".", "b", "..", "..", "c", ""]
• Use a stack to process each part.
• The stack progression will look like: ["a"] -> ["a", "b"] -> ["a"] -> [] -> ["c"]
• The result will be "/c"

Time Complexity: O(n) where n is the length of the path string. We do one pass to split and one pass to process each part.

Space Complexity: O(n) for the stack storage.

Conclusion:

The journey from a brute-force solution to an optimal one teaches us the importance of understanding the problem’s structure.

In this case, using a stack efficiently solved our problem. Remember, the right data structure often leads to an efficient solution!

If you found this post helpful, do follow my blog for more such comprehensive breakdowns and explanations! 📘🌟

Further Learning at DSAGuide.com
For an in-depth exploration of data structures, algorithms, and coding interview solutions, I invite you to visit DSAGuide.com. Elevate your understanding with our detailed guides on essential data structures, algorithms and coding interview problem solving.