1003 检查替换后的词

下面是题目

方法

和1209删除字符串中所有重复项II中的方法一样，我愿意称之为龙珠算法QQ

碰到 abc,删除或递归

代码实现

用了删除和递归两种方法，但是时间都好慢啊。。。

class Solution {
public:

bool isValid(string S) {
    for (int i = 0; i < S.size(); i++)
    {
        if(i>=2&&S[i]=='c'&&S[i-1]=='b'&&S[i-2]=='a')
        {
           S.erase(i-2,3);//使用erase删除
           i=i-3;
        }
    }
    return S.empty();
}
};

递归

bool isValid(string S) {
    for (int i = 0; i < S.size(); i++)
    {
        if(i>=2&&S[i]=='c'&&S[i-1]=='b'&&S[i-2]=='a')
        {
            return isValid(S.substr(0,i-2)+S.substr(i+1));
        }
    }
    return S.empty();
}

一种好方法,根据分析，我们直到只要字符串是正确的，那么c前面必然是b,b前面必然是a，所以说可以真么写，如果是 ababcc这样的话，反正先对第一个c进行操作，操作完后还是abc，所以问题不大

class Solution {
public:
    bool isValid(string S) {
        stack<char> stk;
        for (char c : S) {
            if (c != 'c') {
                stk.push(c);
            } else {
                if (stk.empty() || stk.top() != 'b') return false;
                stk.pop();
                if (stk.empty() || stk.top() != 'a') return false;
                stk.pop();
            }
        }
        return stk.empty();
    }
};