简化路径

题目

71. 简化路径

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

在 Unix 风格的文件系统中规则如下：

  • 一个点 '.' 表示当前目录本身。
  • 此外，两个点 '..' 表示将目录切换到上一级（指向父目录）。
  • 任意多个连续的斜杠（即，'//' 或 '///'）都被视为单个斜杠 '/'。
  • 任何其他格式的点（例如，'...' 或 '....'）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

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

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

示例 1：

输入：path = “/home/“

输出：“/home”

解释： 应删除尾随斜杠。

示例 2：

输入：path = “/home//foo/“

输出：“/home/foo”

解释：多个连续的斜杠被单个斜杠替换。

示例 3：

输入：path = “/home/user/Documents/../Pictures”

输出：“/home/user/Pictures”

解释： 两个点 ".." 表示上一级目录（父目录）。

示例 4：

输入：path = “/../“

输出：“/“

解释：不可能从根目录上升一级目录。

示例 5：

输入：path = “/…/a/../b/c/../d/./“

输出：“/…/b/d”

解释： "..." 在这个问题中是一个合法的目录名。

题解

题解一

本体的难点在于如何理解题意，通过下面这个例子来理解一下

针对 /.../a/../b/c/../d/./ 这个路径

... 代表一个路径

/a/.. 其代表的是目录 a下的上层目录，也就是目录 ...这个目录下，和目录 a是同级目录

同理 /c/.. 代表的是目录目录 b这个目录下，和目录 c是同级目录

所以，/.../a/../b/c/../d/./这个路径最终的目录为 /.../b/d

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
public static String simplifyPath(String path) {
    String[] split = path.split("/");
    Stack<String> stack = new Stack<>();
    stack.push("/");
    for (String s : split) {
        if (s.equals(".") || s.isEmpty()) {
            continue;
        }
        if (!stack.isEmpty() && s.equals("..")) {
            stack.pop();
        } else {
            stack.push(s);
        }
    }
    StringBuilder sb = new StringBuilder();
    for (String s : stack) {
        if (!s.equals("/") && !s.equals("..")) {
            sb.append(s).append("/");
        }
    }
            if (!sb.isEmpty()) {
        sb.deleteCharAt(sb.length() - 1);
    }
    return "/" + sb;
}

image-20241129220304750

题解二

当然，和官方解法一样，用队列也完全OK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static String simplifyPath(String path) {
    String[] names = path.split("/");
    Deque<String> stack = new ArrayDeque<String>();
    for (String name : names) {
        if ("..".equals(name)) {
            if (!stack.isEmpty()) {
                stack.pollLast();
            }
        } else if (!name.isEmpty() && !".".equals(name)) {
            stack.offerLast(name);
        }
    }
    StringBuilder ans = new StringBuilder();
    if (stack.isEmpty()) {
        ans.append('/');
    } else {
        while (!stack.isEmpty()) {
            ans.append('/');
            ans.append(stack.pollFirst());
        }
    }
    return ans.toString();
}