一、题目描述
给你一个字符串 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 风格绝对路径。
二、解题思路
1. 首先，我们可以将给定的路径字符串按’/'进行分割，得到一个字符串数组。
2. 然后，我们可以遍历这个数组，根据规则进行处理：
- 如果是"."，则表示当前目录，我们可以忽略。
- 如果是"…"，则表示上一级目录，我们需要将当前的目录弹出。
- 如果是空字符串，则表示连续的’/'，我们也可以忽略。
- 否则，我们就将当前的目录压入栈中。
3. 最后，我们将栈中的元素拼接成路径字符串，注意，如果栈为空，我们需要返回"/"。
三、具体代码
import java.util.Stack;
public class Solution {
public String simplifyPath(String path) {
String[] parts = path.split("/");
Stack<String> stack = new Stack<>();
for (String part : parts) {
if (part.equals(".") || part.isEmpty()) {
continue;
}
if (part.equals("..")) {
if (!stack.isEmpty()) {
stack.pop();
}
} else {
stack.push(part);
}
}
StringBuilder sb = new StringBuilder();
for (String part : stack) {
sb.append("/").append(part);
}
return sb.length() == 0 ? "/" : sb.toString();
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 分割路径字符串
path.split("/")的时间复杂度是 O(n)，其中 n 是路径字符串的长度。 - 遍历分割后的字符串数组
parts的时间复杂度是 O(m)，其中 m 是数组的长度。在最坏的情况下，m 可以接近 n（当路径中没有 ‘/’ 时）。 - 构建最终路径字符串的时间复杂度是 O(k)，其中 k 是栈中元素的数量。在最坏的情况下，k 可以接近 n（当路径中没有 ‘.’ 或 ‘…’ 时）。
- 综上所述，总的时间复杂度是 O(n + m + k)，在最坏的情况下，可以近似为 O(n)。
2. 空间复杂度
- 分割后的字符串数组
parts占用 O(m) 的空间，其中 m 是数组的长度。 - 栈
stack占用 O(k) 的空间，其中 k 是栈中元素的数量。 StringBuilder占用 O(k) 的空间。- 综上所述，总的空间复杂度是 O(m + k)，在最坏的情况下，可以近似为 O(n)。
五、总结知识点
1. 字符串处理：
- 使用
split方法根据给定的分隔符（在这里是 ‘/’）将字符串分割成数组。 - 使用
equals方法比较字符串是否相等。
2. 数据结构：
- 使用
Stack类来实现一个后进先出（LIFO）的数据结构，用于处理目录的进入和退出。
3. 循环和条件判断：
- 使用
for循环遍历字符串数组。 - 使用
if和else条件判断来执行不同的逻辑，如忽略当前目录（“.”），返回上一级目录（“…”），或者将目录加入栈中。
4. 字符串构建：
- 使用
StringBuilder类来高效地构建最终的路径字符串，因为它允许在不创建新对象的情况下修改字符串内容。
5. 异常处理：
- 在处理 “…” 时，使用
if (!stack.isEmpty())来检查栈是否为空，以避免EmptyStackException。
6. 边界条件处理：
- 在返回最终路径时，检查
StringBuilder的长度是否为0，如果是，则返回根路径 “/”。
7. Java 语法：
- 使用
public class定义一个公共类。 - 使用
public static定义一个公共静态方法。 - 使用
return语句返回方法的结果。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
