题目描述

给定一个绝对路径，请对其化简。

例如：
path = "/home/", => "/home"；
path = "/a/./b/../../c/", => "/c"；

边界情况：

• 你有没有考虑 path = "/../"？这时你需要返回 "/"
• 有些路径可能包含多个连续的'/'，例如 "/home//foo/"。在这种情况下，你需要忽略多余的斜杠，返回 "/home/foo"。

算法

(模拟) $O(n)$

我们可以把整个路径看作是一个动态的“进入某个子目录”或“返回上级目录”的过程。

所以我们可以模拟这个过程，用 res 记录当前的路径位置：

• 如果遇到 ".."，则返回上级目录；
• 如果遇到 "."或多余的斜杠，则不做任何处理：
• 其它情况，表示进入某个子目录，我们在 res 后面补上新路径即可；

时间复杂度分析：整个路径 path 我们只遍历一遍，且 res 添加和删除的路径均是 path 的真子集，其总长度不大于 path 的长度，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    string simplifyPath(string path) {
        if (path.back() != '/') path += '/';
        string res, s;
        for (auto &c : path)
        {
            if (res.empty()) res += c;
            else if (c == '/')
            {
                if (s == "..")
                {
                    if (res.size() > 1)
                    {
                        res.pop_back();
                        while (res.back() != '/') res.pop_back();
                    }
                }
                else if (s != "" && s != ".")
                {
                    res += s + '/';
                }
                s = "";
            }
            else
            {
                s += c;
            }
        }
        if (res.size() > 1) res.pop_back();
        return res;
    }
};