0071.md

71. Simplify Path

Level:

Topic:

Question

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.

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

Intuition

Use deque as stack to store directories and as queue to finalize path\

1. Remove all whitespace and separate the directories by "/"
2. iterate through all directories
   • if it's a regualr directory name, add it to the stack
   • if ".", do nothing
   • if "..", pop the top off the stack if any
3. if the stack is empty, return "/"
4. iterate the stack in its reversed order, (deque is used). and use stringbuilder to construct the final canonical path

Code

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

//     Use string split to separate all directories
//     if directory is invalid (length == 0 || ".")
//         ignore
//     else if directory == ".."
//         pop the stack if stack is not empty
//     else
//         add directory to stack

public String simplifyPath(String path) {
    String [] dirs = path.split("/");

    Deque<String> stack = new ArrayDeque<>();
    for (String dir: dirs) {
        if (dir.length() == 0 || dir.equals("."))
            continue;
        if (dir.equals("..")) {
            if (!stack.isEmpty())
                stack.removeLast();
        }
        else
            stack.addLast(dir);
    }
    if (stack.isEmpty())
        return "/";

    StringBuilder ans = new StringBuilder();
    while (!stack.isEmpty()) {
        ans.append("/");
        ans.append(stack.removeFirst());
    }
    return ans.toString();
}