【数据结构-邻项消除】力扣1003. 检查替换后的词是否有效

给你一个字符串 s ，请你判断它是否 有效 。
字符串 s 有效 需要满足：假设开始有一个空字符串 t = “” ，你可以执行 任意次 下述操作将 t 转换为 s ：

将字符串 “abc” 插入到 t 中的任意位置。形式上，t 变为 tleft + “abc” + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为 空 。
如果字符串 s 有效，则返回 true；否则，返回 false。

示例 1：
输入：s = “aabcbc”
输出：true
解释：
“” -> “abc” -> “aabcbc”
因此，“aabcbc” 有效。

示例 2：
输入：s = “abcabcababcc”
输出：true
解释：
“” -> “abc” -> “abcabc” -> “abcabcabc” -> “abcabcababcc”
因此，“abcabcababcc” 有效。

示例 3：
输入：s = “abccba”
输出：false
解释：执行操作无法得到 “abccba” 。

模拟栈

class Solution {
public:
    bool isValid(string s) {
        string st;
        for(char c : s){
            st.push_back(c);
            if(st.size() >= 3 && st.substr(st.size() - 3, 3) == "abc"){
                st.erase(st.end() - 3, st.end());
            }
        }
        return st.empty();
    }
};

时间复杂度：O(n)，其中 n 是字符串 s 的长度。

空间复杂度：O(n)。栈需要占用 O(n) 的空间。

我们可以采用模拟栈的方法，由于一开始t字符串第一次操作后一定是"abc"，所以我们可以一旦遇到abc，就将它消除。在栈中表现为如果栈顶三个元素为"abc"，那么就将它弹出，最后如果st变为空，则说明可以通过将字符串 “abc” 插入到 t 中的任意位置，得到字符串s。