leetcode：1047. 删除字符串中的所有相邻重复项

题目

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

  1. 输入："abbaca"
  2. 输出："ca"
  3. 解释：
  4. 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

解答 & 代码

解法 0：模拟（超时）

class Solution {
public:
    string removeDuplicates(string s) {
        while(true)
        {
            bool eraseFlag = false;
            int idx = 0;
            while(idx < s.size())
            {
                if(s[idx] == s[idx + 1])
                {
                    s.erase(idx, 2);
                    eraseFlag = true;
                }
                else
                    ++idx;
            }
            if(eraseFlag == false)
                break;
        }
        return s;
    }
};

解法 1：栈

使用栈保存未被删除的字符。遍历字符串，如果当前字符和栈顶元素相同，则消去栈顶，否则将当前元素入栈。

string 本身就有类似栈的入栈、出栈的操作，而结果是要返回字符串，因此直接将 **string** 当作栈

class Solution {
public:
    string removeDuplicates(string s) {
        string result;        // 结果字符串，当作栈
        for(int i = 0; i < s.size(); ++i)
        {
            // 如果栈为空，或者栈顶元素和当前字符不同，则将当前字符入栈
            if(result.size() == 0 || result.back() != s[i])
                result.push_back(s[i]);
            // 否则消去栈顶元素
            else
                result.pop_back();
        }
        return result;
    }
};

复杂度分析：设字符串 s 长为 N

  • 时间复杂度 O(N)：遍历一遍字符串 s
  • 空间复杂度 O(1)：结果字符串不计

执行结果：

执行结果：通过

执行用时：12 ms, 在所有 C++ 提交中击败了 90.39% 的用户
内存消耗：10.8 MB, 在所有 C++ 提交中击败了 69.72% 的用户