LeetCode 71. 简化路径（中）

时刻注意利用栈先进先出的特点，另外这道题中利用字典
dict.get(key, default_value) 函数进行条件判定的方法非常优雅，一定要学会。

题目

以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。

示例

示例 1：

1
2
输入："/home/"
输出："/home"

解释：注意，最后一个目录名后面没有斜杠。

示例 2：

1
2
输入："/../"
输出："/"

解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。

示例 3：

1
2
输入："/home//foo/"
输出："/home/foo"

解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。

示例 4：

1
2
输入："/a/./b/../../c/"
输出："/c"

示例 5：

1
2
输入："/a/../../b/../c//.//"
输出："/c"

示例 6：

1
2
输入："/a//b////c/d//././/.."
输出："/a/b/c"

考察知识点

栈、字符串

核心思想

方法一、直接根据规律进行字符串处理

这道题让简化给定的路径，光根据题目中给的那一个例子还真不太好总结出规律，应该再加上两个例子
path = "/a/./b/../c/", => "/a/c"
path = "/a/./b/c/", => "/a/b/c"
这样我们就可以知道

  • 中间是"."的情况直接跳过。
  • 是".."时删掉它上面挨着的一个路径，且跳过这个。

而下面的边界条件给的一些情况中可以得知

  • 如果是空的话返回"/"
  • 如果有多个"/"只保留一个

那么我们可以把路径看做是由一个或多个"/"分割开的众多子字符串，把它们分别提取出来一一判断处理即可。

方法二、基于栈

一句话解释: 栈解决,把当前目录压入栈中，遇到..弹出栈顶,最后返回栈中元素.

Python版本

  • 方法一的实现
1
2
3
4
5
6
7
class Solution:
    def simplifyPath(self, path: str) -> str:
        r = []
        for s in path.split('/'):
            r = {'':r, '.':r, '..':r[:-1]}.get(s, r + [s])  # get(key, default_value)
        return '/' + '/'.join(r)

执行用时 :44 ms, 在所有 Python3 提交中击败了42.23%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.24%的用户

优化之后的结果，不用每次循环都做split。 推荐该方法，更加简洁，没有用到栈。 

1
2
3
4
5
6
7
class Solution:
    def simplifyPath(self, path: str) -> str:
        r = []
        segments = path.split('/')
        for s in segments:
            r = {'':r, '.':r, '..':r[:-1]}.get(s, r + [s])  # get(key, default_value)  如果key命中 ''、'.'、'..' 这三种特殊情况，就得到特殊处理的结果，分别是r不变、r不变、r最后一个去掉。如果不命中，说明是一个有效的子路径，添加进去，r + [s]。
        return '/' + '/'.join(r)

时间复杂度：\(O(n)\)，n为 / 区间个数。
空间复杂度：\(O(m)\)，m为有效路径层数。
执行用时 :32 ms, 在所有 Python3 提交中击败了89.51%的用户
内存消耗 :13.4 MB, 在所有 Python3 提交中击败了5.24%的用户

  • 方法二的实现
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
26
27
28
29
30
31
32
33
34
35
class Solution:
    def simplifyPath(self, path: str) -> str:
        segments = path.split("/")
        res = []
        for index in range(len(segments)):
            segment = segments[index]
            if segment == "":
                continue
            elif segment == ".":
                continue
            elif segment == "..":
                if len(res):  # 遇到.. 弹出栈顶，最后返回栈中元素。
                    res.pop()
                else:
                    continue
            else:
                res.append(segment)
        return "/" + "/".join(res)



Input = ["/home/", "/../", "/home//foo/", "/a/./b/../../c/", "/a/../../b/../c//.//", "/a//b////c/d//././/.."]
Answer = ["/home", "/", "/home/foo", "/c", "/c", "/a/b/c"]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.simplifyPath(Input[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print([Answer[i]])
            print(reslut)

时间复杂度：\(O(n)\)，n为 / 区间个数。
空间复杂度：\(O(m)\)，m为有效路径层数。
执行用时 :32 ms, 在所有 Python3交中击败了89.51%的用户
内存消耗 :13.5 MB, 在所有 Python3 提交中击败了5.24%的用户

有效语法糖

1、使用字典做判断，非常巧妙。

1
2
3
4
5
6
class Solution:
    def simplifyPath(self, path: str) -> str:
        r = []
        for s in path.split('/'):
            r = {'':r, '.':r, '..':r[:-1]}.get(s, r + [s])  # get(key, default_value)
        return '/' + '/'.join(r)

参考链接

Grandyang LeetCode用户题解