53.简化路径

题目

给你一个字符串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，每次以 item 为单位进行处理（有效的文件名），根据 item 为何值进行分情况讨论:

item 为有效值 : 普通目录名就存入栈中
item 为 .. : 弹出栈顶元素（若存在）
item 为 . 或空字符串 : 不作处理

class Solution {
    fun simplifyPath(path: String): String {
        val stack = ArrayDeque<String>()

        for (part in path.split("/")) {
            when (part) {
                "", "." -> {
                    // 忽略空字符串和当前目录
                }

                ".." -> if (stack.isNotEmpty()) {
                    stack.removeLast()
                }

                else -> stack.addLast(part)
            }
        }

        return "/" + stack.joinToString("/")
    }
}

public String simplifyPath(String path) {
    Deque<String> deque = new ArrayDeque<>();
    int n = path.length();
    for (int i = 1; i < n; i++) {
        if (path.charAt(i) == '/') continue;   // 找到下一个不是"/"的位置
        int j = i + 1;   // j指向下一个位置，双指针！
        while (j < n && path.charAt(j) != '/') j++; // 直到j指向的位置是"/"
        String temp = path.substring(i, j);   // 左闭右开，[i.j)
        if (temp.equals("..")) {     //..的时候，栈内有元素才删
            if (!deque.isEmpty()) {
                deque.pollLast();
            }
        } else if (!(temp.equals("."))) { // .的时候就continue，这里省略了，不是.的时候就进栈
            deque.addLast(temp);
        }
        i = j; //j是指向"/"的，令i=j开始下一轮循环
    }
    StringBuilder ans = new StringBuilder();
    while (!deque.isEmpty()) {  // 还原栈内的路径
        ans.append("/");
        ans.append(deque.pollFirst());
    }
    return ans.length() == 0 ? "/" : ans.toString();  // 栈为空就直接返回"/",否则返回ans.toString()
}

时间 O(n)：split 和遍历各一次
空间 O(n)：栈最多存储所有路径段

下一题

邮箱：charon.chui@gmail.com
Good Luck!