简化路径
难度:
标签:
题目描述
给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。
请注意，返回的 规范路径 必须遵循下述格式：
- 始终以斜杠
'/'开头。 - 两个目录名之间必须只有一个斜杠
'/'。 - 最后一个目录名（如果存在）不能 以
'/'结尾。 - 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含
'.'或'..'）。
返回简化后得到的 规范路径 。
示例 1：
输入：path = "/home/" 输出："/home" 解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入：path = "/../" 输出："/" 解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
示例 3：
输入：path = "/home//foo/" 输出："/home/foo" 解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入：path = "/a/./b/../../c/" 输出："/c"
提示：
1 <= path.length <= 3000path由英文字母，数字，'.'，'/'或'_'组成。path是一个有效的 Unix 风格绝对路径。
代码结果
运行时间: 32 ms, 内存: 15.1 MB
/*
* 思路：
* 1. 使用 Stream API 来处理路径片段。
* 2. 使用 Arrays.stream 将路径分割并过滤空片段和 '.'。
* 3. 使用 reduce 方法累加处理过的片段，处理 '..' 时减去最后的路径。
*/
import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;
public class SimplifyPathStream {
public String simplifyPath(String path) {
List<String> components = Arrays.stream(path.split("/")).filter(s -> !s.isEmpty() && !s.equals(".")).collect(Collectors.toList());
List<String> result = new ArrayList<>();
for (String component : components) {
if (component.equals("..")) {
if (!result.isEmpty()) {
result.remove(result.size() - 1);
}
} else {
result.add(component);
}
}
return "/" + String.join("/", result);
}
}
解释
方法:
该题解使用了栈的思想。遍历输入路径中的每个部分，对于普通的目录名，直接入栈；对于 '.'，不做任何操作；对于 '..'，如果栈不为空，则将栈顶元素弹出。最后将栈中的元素用 '/' 连接起来，并在开头加上 '/' 形成最终的简化路径。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在处理路径分割结果时，空字符串和'.'都被忽略，而没有特别处理？
▷🦆
在使用'..'遍历到栈顶元素时，如果栈为空怎么处理？请问这种情况在实际路径中代表什么含义？
▷🦆
路径中出现的额外斜杠（例如'//'或'///'）在代码中是如何被处理的？
▷🦆
请问在实现时为什么选择使用栈这种数据结构？有没有其他数据结构可以达到相同的效果？
▷