Given an absolute path for a file (Unix-style), simplify it.
For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"
Solution1：stack
思路： 依次push存進(jìn)stack中松蒜，若..則pop
Note： 利用Deque作為stack操作時(shí)，操作都在head垢粮，pop() == removeFirst()因篇，push() == addFirst()诬辈，所以最后遍歷Deque(作為stack)時(shí)鞋仍，是從stack頂?shù)絪tack底，結(jié)果需要reverse, 或insert(0, str)
Time Complexity: O(N) Space Complexity: O(N)
Solution2：linkedlist
思路： 依次append存進(jìn)list中珊豹，若..則removeLast
Note： 這樣最后遍歷Deque(作為list)時(shí)，正序即可
Time Complexity: O(N) Space Complexity: O(N)
Solution1 Code：
class Solution {
public String simplifyPath(String path) {
Deque<String> stack = new ArrayDeque<String>();
// to simplify the result stack by removing redundant path
for(String str: path.split("/")) {
if(str.equals("..")) {
if(!stack.isEmpty()) stack.pop(); // pop() == removeFirst()
}
else if(str.equals(".") || str.isEmpty()) continue;
else stack.push(str); // push() == addFirst()
}
//prepare the result
StringBuilder result = new StringBuilder("");
for(String str: stack) result.insert(0, str).insert(0, "/");
return result.length() == 0 ? "/": result.toString();
}
}
Solution2 Code：
class Solution {
public String simplifyPath(String path) {
Deque<String> list = new LinkedList<>();
// to simplify the result list by removing redundant path
for(String str: path.split("/")) {
if(str.equals("..")) {
if(!list.isEmpty()) list.removeLast();
}
else if(str.equals(".") || str.isEmpty()) continue;
else list.add(str);
}
//prepare the result
StringBuilder result = new StringBuilder("");
for(String str: list) result.append("/").append(str);
return result.length() == 0 ? "/": result.toString();
}
}
