[leetcode] 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 风格绝对路径。

解题方法

栈

我们将path以'/'作为分隔符，将'/'之间的字符串str加入到栈中。由于str存在''、.、..几种特殊字符串。所以需要按以下方式处理：

• 当str = ""时，str不加入栈。
• 当str = "."时，str不加入栈。
• 当str = ".."时，栈顶有元素则栈顶元素出栈，否则不进行处理。
• 当str等于其他字符串时，str加入栈。

最后我们依次将栈顶元素出栈，出栈的str加入到规范路径末尾，出栈结束即可求得规范路径。

java代码

public String simplifyPath(String path) {
    int i = 0;
    String str = "";
    Stack<String> stack = new Stack<>();
    while (i < path.length()) {
        if (path.charAt(i) == '/') {
            if (str.equals(".") || str.equals("")) {

            } else if (str.equals("..")) {
                if (!stack.isEmpty()) {
                    stack.pop();
                }
            } else {
                // 每个入栈的字符串前面加上'/'，方便后续简化路径的处理
                stack.push("/" + str);
            }
            str = "";
        } else {
            str += path.charAt(i);
        }
        i++;
    }
    // path最后一个字符不为'/'时，最后的str需要单独处理
    if (str.equals(".") || str.equals("")) {

    } else if (str.equals("..")) {
        if (!stack.isEmpty()) {
            stack.pop();
        }
    } else {
        stack.push("/" + str);
    }
    StringBuilder builder = new StringBuilder();
    while (!stack.isEmpty()) {
        builder.insert(0, stack.pop());
    }
    // 当简化路径为空时，返回根目录'/'
    return builder.toString().equals("") ? "/" : builder.toString();
}

复杂度分析

• 时间复杂度：$O(N)$，需要遍历一次path。$N$为path长度。
• 空间复杂度：$O(N)$，需要提供栈存储path分割后的字符串，还需要返回结果字符串。

• 个人小游戏