53-删除字符串中的所有相邻重复项

自己的做法

算法思想

遍历字符串，将字符依次入栈，对于当前遍历到的字符，如果栈顶字符和该字符相同，则弹出栈顶元素。

遍历结束后，将字符依次出栈，连接成字符串。

需要注意一个问题：如果从头到尾遍历字符串，那么栈顶到栈底是结果字符串的尾到头。也就是正好反过来。

所以出栈时，应该将出栈的字符连接到字符串前面。

也可以从尾到头遍历字符串，那么出栈的字符就应连接到字符串末尾。

算法实现

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> stack;
        //从尾到头遍历字符串
        for(int i = s.size() - 1; i >= 0;i--) {
            if(!stack.empty() && stack.top() == s[i]) {
                stack.pop();
            } else {
                stack.push(s[i]);
            }
        }
        s = "";
        while (!stack.empty()) {
            s.push_back(stack.top());
            stack.pop();
        }
        return s;
    }
};

性能分析

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

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

参考做法

算法思想

C++ 的std:string类本身就带有类似栈的pop和push操作。所以可以把结果字符串res本身作为一个栈。

即当res的尾字符和当前遍历到的字符相等时，就从res中去掉该字符，使用pop_back()。

否则将该字符添加到末尾,使用push_back()。

算法实现

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

性能分析

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

空间复杂度：$O(1)$。注意，结果字符串本身不计入空间复杂度。