题目描述

题目链接

https://leetcode.cn/problems/simplify-path/

思路

我们首先将给定的字符串根据「」分割成一个由若干字符串组成的列表，记为。根据题目中规定的「规范路径的下述格式」，中包含的字符串只能为以下几种：

• 空字符串。例如当出现多个连续的「」，就会分割出空字符串；
• 一个点「」；
• 两个点「」；
• 只包含英文字母、数字或「」的目录名。

对于「空字符串」以及「」，我们实际上无需对它们进行处理，因为「空字符串」没有任何含义，而「」表示当前目录本身，我们无需切换目录。对于「」或者「目录名」，我们则可以用一个栈来维护路径中的每一个目录名。当我们遇到「」时，需要将目录切换到上一级，因此只要栈不为空，我们就弹出栈顶的目录。当我们遇到「目录名」时，就把它放入栈。

这样一来，我们只需要遍历中的每个字符串并进行上述操作即可。在所有的操作完成后，我们将从栈底到栈顶的字符串用「」进行连接，再在最前面加上「」表示根目录，就可以得到简化后的规范路径。

代码实现

public String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    // 按下划线切分，即便是多个///也会被分割为空字符串
    String[] names = path.split("/");
    for (String name : names) {
        if (".".equals(name) || "".equals(name)) {
            continue;
        }
        // 返回上一级
        if ("..".equals(name)) {
            if (!stack.isEmpty()) {
                stack.pop();
            }
        } else {
            // 将目录名入栈
            stack.push(name);
        }
    }
    // 拼接路径
    StringBuilder ans = new StringBuilder();
    if (!stack.isEmpty()) {
        while (!stack.isEmpty()) {
            ans.append("/");
            ans.append(stack.pollLast());
        }
    } else {
        ans.append("/");
    }
    return ans.toString();
}

复杂度分析

• 时间复杂度：，其中是字符串的长度。
• 空间复杂度：。我们需要的空间存储中的所有字符串。