Simplify Path

NeetCode: Simplify Path · LeetCode: 71. Simplify Path · Difficulty: Medium

Given an absolute Unix-style path, return its simplified canonical path. A single . means the current directory, .. means go up one directory (staying at the root if already there), and multiple consecutive slashes count as one. Any other sequence of dots, such as ..., is an ordinary directory name. The result starts with /, separates directories with a single /, has no trailing / (except for the root itself), and contains no . or .. parts.

Example

Text

Input:  path = "/home/"                          Output: "/home"
Input:  path = "/home//foo/"                     Output: "/home/foo"
Input:  path = "/../"                            Output: "/"
Input:  path = "/.../a/../b/c/../d/./"           Output: "/.../b/d"

Brute force: keep rewriting until nothing changes

Split on / and drop the empty parts and . parts. Then repeatedly find the first ..: if it is the very first component it has nothing to go up from, so delete only that component; otherwise delete it together with the component before it. Repeat until no .. remains. String.split("/") cuts the path at every /; consecutive slashes produce empty parts, and trailing empty parts are dropped. String.join("/", parts) joins a collection with a separator. parts.remove(pos) with an int argument removes by position. Each removal is an ArrayList.remove plus a rescan from the start, so the total is quadratic.

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    public String simplifyPath(String path) {
        List<String> parts = new ArrayList<>();
        for (String p : path.split("/")) {
            if (!p.isEmpty() && !p.equals(".")) {
                parts.add(p);
            }
        }
        int pos;
        while ((pos = parts.indexOf("..")) >= 0) {
            if (pos == 0) {
                parts.remove(0);
            } else {
                parts.remove(pos);      // remove("..")
                parts.remove(pos - 1);  // remove the directory before it
            }
        }
        return "/" + String.join("/", parts);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.simplifyPath("/home/"));
        System.out.println(s.simplifyPath("/home//foo/"));
        System.out.println(s.simplifyPath("/../"));
        System.out.println(s.simplifyPath("/.../a/../b/c/../d/./"));
        System.out.println(s.simplifyPath("/a/./b/../../c/"));
    }
}

Output

/home
/home/foo
/
/.../b/d
/c

Time: O(n^2) in the worst case (many .., each triggering a rescan and shifting removes). Space: O(n).

Optimal: one pass with a stack

Walk the components left to right and keep a stack of directory names. An empty part or . is ignored. .. pops the top if there is one (at the root there is nothing to pop, so it is ignored). Anything else, including ..., is pushed. This stack is an ArrayDeque used from the tail: addLast pushes, pollLast pops, and iteration runs from first to last, so String.join sees the directories in path order. (push and pop work on the head and would reverse the order.) Joining the stack with / after a leading / gives the canonical path, and an empty stack yields /.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>(); // top of the stack is the last element
        for (String part : path.split("/")) {
            if (part.isEmpty() || part.equals(".")) {
                continue;
            }
            if (part.equals("..")) {
                stack.pollLast(); // returns null when empty, so ".." at the root is ignored
            } else {
                stack.addLast(part);
            }
        }
        return "/" + String.join("/", stack);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.simplifyPath("/home/"));
        System.out.println(s.simplifyPath("/home//foo/"));
        System.out.println(s.simplifyPath("/../"));
        System.out.println(s.simplifyPath("/.../a/../b/c/../d/./"));
        System.out.println(s.simplifyPath("/a/./b/../../c/"));
    }
}

Output

/home
/home/foo
/
/.../b/d
/c

Time: O(n), each component is pushed and popped at most once. Space: O(n).