59-简化路径

​ 同时保证，path是一个有效的Unix路径。

自己的做法，太太太繁琐了。

思路也不对，一直再处理各种特殊情况。就不贴这了。

参考做法

算法思想

使用一个栈来存放有效路径。

遍历path字符串，

可以发现，当遇到一个 /时，说明前面是一个路径。这个路径有三种情况：..、.和有效路径。

使用一个字符串dir来存放碰到这个/之前的路径。

如果是..，那么就弹出栈顶元素(需判断栈是否为空)，如果是.，则直接跳过，如果是有效元素，就将dir添加到栈中。

然后清空dir字符串。

当遇到其他字符时，就添加到dir末尾。

需要注意的是：因为给定路径path的末尾有可能没有/，所以例如/a/..这种就会出现错误，所以可以手动在path后添加 一个/，来避免这种情况。

遍历结束后，如果栈为空，则直接返回/，否则依次弹栈连接到结果字符串res。

在连接时注意：栈顶元素应该在末尾，也就是从栈底到栈顶，目录是主次递进的。所以每次连接都需要添加到res开头。

算法实现

class Solution {
public:
    string simplifyPath(string path) {
        stack<string> s;
        string dir = "";
        path  = path + "/";
        for(char ch : path) {
            if(ch == '/') {
                if(dir == "..") {
                    if(!s.empty()) s.pop();
                } else if(dir != "." && !dir.empty()) {
                    s.push(dir);
                }
                dir.clear();
            } else {
                dir += ch;
            }
        }
        if(s.empty()) {
            return "/";
        }
        string res = "";
        while (!s.empty()) {
            res = "/" + s.top() + res;
            s.pop();
        }
        return res;
    }
};

性能分析

时间复杂度：遍历一遍字符串，又依次弹出栈顶元素，为$O(n)$，n为path字符串长度。

空间复杂度：$O(n)$。使用栈来存放字符。