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