Question

link

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".

Stats

Frequency 1
Difficulty 3
Adjusted Difficulty 4
Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a very difficult string question. I read this blog and then understands the question. The solution is just straight-forward without any fancy algo/thinkings.


[解题思路]
利用栈的特性，如果sub string element
1. 等于“/”，跳过，直接开始寻找下一个element
2. 等于“.”，什么都不需要干，直接开始寻找下一个element
3. 等于“..”，弹出栈顶元素，寻找下一个element
4. 等于其他，插入当前elemnt为新的栈顶，寻找下一个element

最后，再根据栈的内容，重新拼path。这样可以避免处理连续多个“/”的问题。

Solution

Simply make use of stack and read thru all substrings seperated by /.

Code

public String simplifyPath(String path) {
    Stack<String> stack = new Stack<String>();
    String[] list = path.split("/");
    for(String cur: list) {
        if (cur.equals("/") || cur.equals(".")
            || cur.equals("")) continue;
        if (cur.equals("..")) {
            if (! stack.isEmpty()) stack.pop();
        } else stack.push(cur);
    }
    String ans = "";
    if (stack.isEmpty()) return "/";
    while (! stack.isEmpty()) {
        ans = "/" + stack.pop() + ans;
    }
    return ans;
}