题目
思路
这个题和逆波兰表达式求值很想,都是通过使用栈来实现。
对于给定的绝对路径,首先可以使用 “/” 将其分割,分割后的字符串共包括四种情况:
- 空字符串(例如当绝对路径为"//"时,分割后为空字符串)
- " . "
- “. .”
- 目录名
对于第一种和第二种情况,即「空字符串」和 “.”,无需进行处理,因为「空字符串」没有任何含义,而 “.” 表示当前目录本身,无需切换目录。
对于 第三种情况(即". ."),表示返回上一级目录,因此当栈不为空时,直接弹出一个目录名即可;对于第四种情况,直接将该目录名入栈即可。
代码
这里列出 java 代码
public String simplifyPath (String path){
// 定义栈来处理 path
Deque<String> stack = new ArrayDeque<>();
// 按 “/” 分割,分割后的结果包括 空字符串、"."、 ".." "目录名"
String[] names = path.split("/");
for (String name : names) {
// 空字符串和".", 直接跳过
if (name.length() > 0 && !name.equals(".")) {
// 如果是 "..",说明要返回上一级
if (name.equals("..")) {
// 栈非空时弹出一个元素,模拟返回上一级
if (!stack.isEmpty()) {
stack.pollLast();
}
}
// 若是目录名,则入栈
else {
stack.offerLast(name);
}
}
}
// 保存最终路径
StringBuilder sb = new StringBuilder();
if (!stack.isEmpty()) {
while (!stack.isEmpty()) {
sb.append("/");
sb.append(stack.pollFirst());
}
}
else {
sb.append("/");
}
return sb.toString();
}
时空复杂度
时间复杂度:O(n),其中 n 是字符串的长度。需要遍历字符串的每个字符,对于每个字符,入栈和出栈操作的时间复杂度为 O(1),因此总的时间复杂度为 O(n)。
空间复杂度:O(n),其中 n 是字符串的长度。空间复杂度主要取决于字符串的分割和栈的使用。分割字符串需要 O(n) 的空间,栈的最大空间大小为 O(n)。因此空间复杂度为 O(n)。