题目描述

题目链接

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为更加简洁的规范路径。

在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。任意多个连续的斜杠（即，’//‘）都被视为单个斜杠 ‘/‘ 。 对于此问题，任何其他格式的点（例如，’…’）均被视为文件/目录名称。

请注意，返回的 规范路径 必须遵循下述格式：

始终以斜杠 ‘/‘ 开头。
两个目录名之间必须只有一个斜杠 ‘/‘ 。
最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。

样例

1
2
3
4
5
示例 1：

输入：path = "/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。 
1
2
3
4
5
示例 2：

输入：path = "/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根目录是你可以到达的最高级。
1
2
3
4
5
示例 3：

输入：path = "/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
1
2
3
4
示例 4：

输入：path = "/a/./b/../../c/"
输出："/c"

算法1

(模拟) $O(n)$

本题本质上是模拟进入 Unix 系统路径的方法，只需要按照规定将所有步骤执行，遍历一遍字符串即可

需要注意的是一些边界情况：

  • 在根目录时输入了 /../, 这种情况下需要返回根目录/，因为根目录无法再向上回到更上级的目录
  • 有些路径包含连续的 ////, 应该去掉重复的 /

思路： 可以看出，所有的有效路径都是在两个/中产生的，所以我们应该将 /视为分界点，统计在两个 / 之间出现的字符串，按照规定模拟即可

规则：

  • 当两个/之间的字符串为 . 或 为空时，说明要么表示在当前目录不动，要么表示有多个/,这种情况不必更新最终路径
  • 当两个/之间的字符串为 ..时，说明不仅不应该加入新的路径，反而应当将最终路径向前回退至上一个 /
  • 当/之间的字符串为正常路径时，应当更新最终路径，需要注意的时每次更新最终路径时按照/路径名的方式更新

C++ 代码

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
class Solution {
public:
    string simplifyPath(string path) {
        string res, seg;
        if( path.back() != '/') path += '/';

        for(auto c : path)
        {
            if( c != '/') seg += c;
            else
            {
                if( seg == "..")
                {
                    while( res.size() && res.back() != '/') res.pop_back(); //每当到尚未回退至上一个/时，持续回退
                    if(res.size()) res.pop_back(); // 删去剩余的一个 /
                }
                else if( seg != "." && seg != "")
                {
                    //当 seg 为正常路径时，更新最终路径
                    res += '/' + seg;
                }
                seg.clear(); //每次需要清空两个 / 之间的字符
            }
        }

        if( res.empty()) res += '/';  //如果执行完之后 res 为空，说明他在当前路径，应该加上 /

        return res;
    }
};