leetcode 71. Simplify Path(Unix下简化路径)
程序员文章站
2022-05-22 15:04:04
...
算法思路:
首先设置一个String类型的栈。用spilt方法,对path进行分割,以“/”
为分隔符分割得到一组字符串。接着遍历这组字符串,遇到空字符串(“”)
和当前目录(".")
跳过,若字符串为".."
且栈不为空时弹栈,若字符串为".."
且栈为空则跳过,其他情况则将元素压栈(if…else if…else…)。最后将栈中的元素和"/"按顺序组合成一条有效路径,当路径为空时,返回根目录,否则返回路径。
该算法时间复杂度O(n),空间复杂度(n)。参考代码:
//leetcode 71. Simplify Path
public static String simplifyPath(String path) {
Stack<String> stack = new Stack<String>();
String[] tokens = path.split("/");
for(int i=0;i<tokens.length;i++){
if(tokens[i].equals("")||tokens[i].equals("."))
continue;
if(tokens[i].equals("..")&&!stack.isEmpty()){
stack.pop();
}else if(tokens[i].equals("..")&&stack.isEmpty()){
continue;
}else{
stack.push(tokens[i]);
}
}
StringBuilder s = new StringBuilder("");
while(!stack.isEmpty()){
String str = "/"+stack.pop();
s.insert(0, str);
}
if(s.length()==0)
return "/";
return s.toString();
}