71. 简化路径

1. 题目

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 '/' 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，'//'）都被视为单个斜杠 '/' 。 对于此问题，任何其他格式的点（例如，'...'）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

  • 始终以斜杠 '/' 开头。
  • 两个目录名之间必须只有一个斜杠 '/' 。
  • 最后一个目录名（如果存在）不能 以 '/' 结尾。
  • 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 '.' 或 '..'）。

返回简化后得到的 规范路径 。

示例 1：

1
2
3
输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
3
输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。

示例 3：

1
2
3
输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1
2
输入：path = "/a/./b/../../c/"
输出："/c"

提示：

  • 1 <= path.length <= 3000
  • path 由英文字母，数字，'.'，'/' 或 '_' 组成。
  • path 是一个有效的 Unix 风格绝对路径。

2. 思路

  • 已知题目要求将路径进行格式化，格式化后会消灭掉重复的/和.以及压缩..等命令，同时题目要求将三个.以上视为文件名称（一定程度上降低了难度）
  • 初始化双向队列deque变量（一方面可以用来当栈使用，另一方面可以当做队列来使用）
  • 将原路径path按照/符号进行拆分得到arr字符串数组
  • 遍历该字符串数组，进行路径优化
    • 当栈为空时
      • 如果字符串为.或/或..，则不写入栈，因为没有意义
      • 如果字符串为普通文件名字，则写入栈
    • 当栈不为空时
      • 如果字符串为..，则弹出上一个文件，因为..符号代表返回上一级
      • 如果字符串为/或.时，则不写入栈，因为没有意义
      • 如果为其他字符串时，则写入栈
  • 完成遍历后，按顺序出栈，使用/符号进行间隔，需要注意的是，最后一个目录后边没有斜杆（题目要求）

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public String simplifyPath(String path) {
        var deque = new ArrayDeque<String>();

        var result = new StringBuilder("/");
        var arr = path.split("/");

        for (var i = 1; i < arr.length; ++i) {
            var str = arr[i];
            if (deque.isEmpty()) {
                if ("..".equals(str) || ".".equals(str) || str.length() == 0) {
                    continue;
                }
                deque.push(str);
            } else {
                if ("..".equals(str)) {
                    deque.pop();
                } else if (str.length() == 0 || ".".equals(str)) {
                    continue;
                } else {
                    deque.push(str);
                }
            }
           
        }

        while (!deque.isEmpty()) {
            result.append(deque.pollLast());
            if (deque.size() != 0) {
                result.append("/");
            }
        }

        return result.toString();
    }
}

4. 复杂度

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

image-20230908215550715