71.简化路径

题目: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"

解释："..." 是此问题中目录的有效名称。

• 提示：

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

思路

要将给定的 Unix 风格路径 path 转化为更加简洁的规范路径，可以按以下步骤进行处理：

1. 分割路径：首先，通过斜杠 / 将路径分割成多个部分。
2. 使用栈来处理路径：初始化一个空栈，用来处理目录变化。
   • 如果遇到单个点 .，表示当前目录，跳过它。
   • 如果遇到两个点 ..，表示回到上一级目录，弹出栈顶的元素（如果栈不为空）。
   • 如果遇到其他目录名，将其压入栈中。
3. 构建规范路径：将栈中的元素用 / 连接起来，形成最终的规范路径。

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

代码

public String simplifyPath(String path) {
    Stack<String> pathStack = new Stack<>();
    String[] split = path.split("/");
    StringBuilder result = new StringBuilder();
    for (String s : split) {
        if (s.equals("..")) {
            // 如果部分是".."，并且栈不为空，弹出栈顶元素（表示返回上一级目录）
            if (!pathStack.isEmpty()) {
                pathStack.pop();
            }
        } else if (!s.isEmpty() && !s.equals(".")) {
            // 如果部分不是空字符串且不是"."（表示当前目录），将其压入栈中
            pathStack.push(s);
        }
    }
    for (String s : pathStack) {
        result.append("/").append(s);
    }
    return result.isEmpty() ? "/" : result.toString();
}