力扣(LeetCode)71. 简化路径(C++)

模拟

对于路径 $path$ ，遇到 ${}^{\prime }{/}^{\prime }$ 则操作，遇到其他字符则保存名字。操作有如下几种:
1.名字是 $"."$ 或 $""$ 不操作，前者表示在当前目录，后者表示遇到重复 $"/"$ 。
2.名字是 $".."$ ，删除 $ans$ 的上一个目录名，如果 $ans$ 删空了。停止删除。
3.其他名字，答案加入 $"/name"$ ， $name$ 加入答案后，记得清空 $name$ 。

最后，特判 $ans$ 为空，说明在根目录，返回 $/$ ，其他情况返回 $ans$ 即可。

class Solution {
public:
    string simplifyPath(string path) {
        string ans, name;
        if(path.back()!='/') path += '/';
        for(auto& c:path){
            if('/'!=c) name+=c;
            else{
                if(".."==name) {
                    while(ans.size()&&ans.back()!='/') ans.pop_back();
                    if(ans.size()) ans.pop_back();
                }else if("."!=name&&""!=name) {
                    ans += '/'+name;
                }
                name.clear();
            }
        }
        if(ans.empty()) ans += '/';
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度 $O(n)$ ，$path$ 的长度 $n$ ，每个字符最多进栈出栈一次，时间复杂度 $O(n)$ 。

空间复杂度 $O(n)$ ，最坏空间复杂度 $O(n)$ 。

致语

理解思路很重要。
欢迎读者在评论区留言，答主看到就会回复的。

AC