71 Simplify Path

71. Simplify Path

1. Question

Given an absolute path for a file (Unix-style), simplify it.

For example, path="/home/", =>"/home" path="/a/./b/../../c/", =>"/c"

Corner Cases:

• Did you consider the case where path ="/../"? In this case, you should return"/"

• Another corner case is the path might contain multiple slashes '/'together, such as"/home//foo/"In this case, you should ignore redundant slashes and return "/home/foo".

2. Implementation

思路：根据题目的例子，我们知道" "， ".", ".."这三种情况不会出现在结果里，所以把它们存在HashSet里。如果我们遇到".."， 我们需要返回上一级目录，所以需要利用stack。最后需要将stack的结果用“/"隔开，注意stack存储结果的顺序和实际的结果是相反的。

class Solution {
    public String simplifyPath(String path) {
        Set<String> set = new HashSet<>();
        set.add(".");
        set.add("..");
        set.add("");

        Stack<String> stack = new Stack<>();

        for (String dir : path.split("/")) {
            if (dir.equals("..") && !stack.isEmpty()) {
                stack.pop();
            }
            else if (!set.contains(dir)) {
                stack.push(dir);
            }
        }

        StringBuilder res = new StringBuilder();
        while (!stack.isEmpty()) {
            res.insert(0, stack.pop());
            res.insert(0, "/");
        }
        return res.length() == 0 ? "/" : res.toString();
    }
}

3. Time & Space Complexity

时间和空间都是O(n)