分析

• 本题的考点：栈。

• 可以将字符串按照/分成多个字符串，然后依次考察每个字符串，如果是正常文件直接入栈；如果是..，弹出栈顶元素；如果是/或者.或者空字符串不需要操作。

• 对于c++来说，没有库函数直接将字符串按照某个字符分割，我们直接遍历字符串进行求解。对于Java可以使用split函数对字符串进行分割。

代码

• C++

class Solution {
public:
    string simplifyPath(string path) {

        string res, name;  // name是两个/之间的内容
        if (path.back() != '/') path += '/';  // 为了方便处理最后一个目录
        for (auto c : path) {
            if (c != '/') name += c;
            else {
                if (name == "..") {  // 例如/a/bc/..
                    while (res.size() && res.back() != '/') res.pop_back();  // 去掉bc
                    if (res.size()) res.pop_back();  // 去掉/
                } else if (name != "." && name != "") {
                    res += '/' + name;
                }
                name.clear();
            }
        }

        if (res.empty()) res = "/";  // "/../"
        return res;
    }
};

• Java

class Solution {
    public String simplifyPath(String path) {

        String[] sl = path.split("/");

        Stack<String> stk = new Stack<>();  // 不能用Deque，否则最后结果是反的
        for (String s : sl)
            if (!s.equals(".") && !s.equals("..") && !s.equals("")) stk.push(s);
            else if (s.equals("..") && !stk.isEmpty()) stk.pop();

        return "/" + String.join("/", stk);
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为字符串长度。因为每个字符最多进栈出栈一次。

• 空间复杂度：$O(n)$。