71. Simplify Path

Published on May 14, 2023

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.

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:

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

Return the simplified canonical path**.

Algorithm

At first try, I wanted to handle the "/" and tried push the "." and "/" into stack due to the calculator question using stack.(push the operands into stack). This makes things complicated.

Second time I tired to solve it this morning(after 2 days), read again the question, I found that we could use split function in Java String, and thus we could only handle dots and double dots. Stack only stores the words.

If we get one dot, we do nothing and if there are two dots string, we pop one word from stack, because two dots means going one up level.

Finally we traverse all the remaining words in the stack to get the result.

Code

class Solution {
    public String simplifyPath(String path) {
        String[] dirs = path.split("/");
        StringBuilder sb = new StringBuilder();
        Stack stack = new Stack();
        int index = 0;
        while (index < dirs.length) {
            String cur = dirs[index++];
            if (!"".equals(cur) && !".".equals(cur)) {
                continue;
            } else if ("..".equals(cur)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(cur);
            }
        }
        List<String> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            list.add((String)stack.pop());
        }
        for (int i = list.size() - 1; i >= 0; i--) {
            sb.append("/");
            sb.append(list.get(i));
        }
        return sb.toString() == "" ? "/" : sb.toString();
    }
}

While this code can be slightly optimized from line19, where the result is being constructed.

class Solution {
    public String simplifyPath(String path) {
        String[] dirs = path.split("/");
        StringBuilder sb = new StringBuilder();
        Stack stack = new Stack();
        int index = 0;
        while (index < dirs.length) {
            String cur = dirs[index++];
            if ("".equals(cur) || ".".equals(cur)) {
                continue;
            } else if ("..".equals(cur)) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                stack.push(cur);
            }
        }
       while (!stack.isEmpty()) {
           sb = "/" + stack.pop() + sb;
       }
        return sb.toString() == "" ? "/" : sb.toString();
    }
}