栈
我们将path
以'/'
作为分隔符,将'/'
之间的字符串str
加入到栈中。由于str
存在''
、.
、..
几种特殊字符串。所以需要按以下方式处理:
- 当
str = ""
时,str
不加入栈。 - 当
str = "."
时,str
不加入栈。 - 当
str = ".."
时,栈顶有元素则栈顶元素出栈,否则不进行处理。 - 当
str
等于其他字符串时,str
加入栈。
最后我们依次将栈顶元素出栈,出栈的str
加入到规范路径末尾,出栈结束即可求得规范路径。
java代码
public String simplifyPath(String path) {
int i = 0;
String str = "";
Stack<String> stack = new Stack<>();
while (i < path.length()) {
if (path.charAt(i) == '/') {
if (str.equals(".") || str.equals("")) {
} else if (str.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
// 每个入栈的字符串前面加上'/',方便后续简化路径的处理
stack.push("/" + str);
}
str = "";
} else {
str += path.charAt(i);
}
i++;
}
// path最后一个字符不为'/'时,最后的str需要单独处理
if (str.equals(".") || str.equals("")) {
} else if (str.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push("/" + str);
}
StringBuilder builder = new StringBuilder();
while (!stack.isEmpty()) {
builder.insert(0, stack.pop());
}
// 当简化路径为空时,返回根目录'/'
return builder.toString().equals("") ? "/" : builder.toString();
}
复杂度分析
- 时间复杂度:
O
(
N
)
O(N)
O(N),需要遍历一次
path
。 N N N为path
长度。 - 空间复杂度:
O
(
N
)
O(N)
O(N),需要提供栈存储
path
分割后的字符串,还需要返回结果字符串。
- 个人小游戏