[Lc]71简化路径

题目

题解

• 时间复杂度$O(N)$，遍历path
• 空间复杂度$O(N)$，两个n，t暂存路径，res存结果

class Solution {
public:
    string simplifyPath(string path) {
        string res, tmp;
        if(path.empty()) return res;//特殊情况
        stringstream ssp(path);//用stringstream将输入的路径切割
        vector<string> t;//用vector存每个路径，其实原理上应该用stack，但是最后转化成字符串res需要从头遍历，用res更好
        while(getline(ssp, tmp, '/')){//用/切割字符串
            if(tmp == "" || tmp == ".") continue;//若为空或者为.，直接跳过
            else if(tmp == ".." && t.empty()) continue;//为..，且t为空，也跳过
            else if(tmp == ".." && !t.empty()) t.pop_back();//若为..且t中还有值，则弹出栈顶
            else t.push_back(tmp);//其他情况就把字符串压入栈
        }
        for(auto& s:t){
            res += "/" + s;
        }//将t中字符串挨个取出放入res，记得要加/
        return res.empty()? "/" : res;//若t为空返回一个根目录，否则返回res
    }
};