71. Simplify Path

问题

Given an absolute path for a file (Unix-style), simplify it.

例子

path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

分析

首先要明确下面几个规则：

• 路径末尾的/可以删除；
• ./指的是当前路径，可以删除；
• ../指的是上一级路径，/a/b/../相当于/a；
• /../可以被缩减为/。

方法一

首先实现一个string的split方法，把字符串根据'/'分各个成若干字符串。创建一个栈stk，遍历分割后的字符串s：

• 如果s是.，忽略，直接遍历下一个字符串；
• 如果s是..并且栈不为空，将栈顶弹出；
• 否则将字符串入栈。

最后逆序输出栈的元素，并且用/分割，即可得到简化后的路径。栈可以用vector来模拟，这样就可以直接顺序访问元素了，不需要一个一个弹出再逆序输出。

方法二

用string的getline方法来分割字符串

要点

• 字符串分割
• 栈

时间复杂度

O(n)

空间复杂度

O(n)

代码

方法一

class Solution {
public:
    string simplifyPath(string path) {
        vector<string> strs;
        split(path, "/", strs);
        vector<string> simplifiedStrs;
        for (const string &str : strs) {
            if (str == "" || str == ".") continue;
            else if (str == "..") {
                if (!simplifiedStrs.empty())
                    simplifiedStrs.pop_back();
            }
            else simplifiedStrs.push_back(str);
        }
        string simplifiedPath;
        for (const string &str : simplifiedStrs)
            simplifiedPath += "/" + str;
        if (simplifiedPath.empty())
            simplifiedPath = "/";
        return simplifiedPath;
    }
    
private:
    void split(const std::string &s, const std::string &delim, std::vector<std::string> &res) {  
        size_t last = 0;  
        size_t index = s.find_first_of(delim, last);  
        while (index != std::string::npos) {  
            res.push_back(s.substr(last, index - last));  
            last = index+1;  
            index = s.find_first_of(delim, last);  
        }  
        if (index-last > 0)  
            res.push_back(s.substr(last, index - last));  
    }
};

方法二

class Solution {
public:
    string simplifyPath(string path) {
        string res, tmp;
        vector<string> stk;
        stringstream ss(path);
        while (getline(ss, tmp, '/')) {
            if (tmp == "" || tmp == ".") continue;
            if (tmp == ".." && !stk.empty()) stk.pop_back();
            else if (tmp != "..") stk.push_back(tmp);
        }
        for (const auto &str : stk) res += "/" + str;
        return res.empty() ? "/" : res;
    }
};