55-整理字符串

自己的做法

算法思想

C++ std:string类有pop_back和push_back方法。分别代表弹出末尾字符和向末尾插入一个字符。

定义结果字符串res，初始为空字符串。

对于相邻的两个字符，无论大写字母在前，对应的小写字母在后，还是反过来。这两个字符都需要被删除。

所以不管顺序，将两个字符都化成小写，同时这两个字母本身不能相同，那么就符合删除的条件。

如果不符合，那么就将当前字符添加到res后。

算法实现

class Solution {
public:
    string makeGood(string s) {
        string res = "";
        for(char ch : s) {
            if(!res.empty() && tolower(ch) == tolower(res.back()) && ch != res.back()) {
                res.pop_back();
            } else {
                res.push_back(ch);
            }
        }
        return res;
    }
};

性能分析

时间复杂度：$O(n)$。

空间复杂度：$O(1)$。

和参考做法的代码一模一样！