71-检查替换后的词是否有效

自己的做法

算法思想

类似于消消乐，当遇到一个连续的abc就去掉，遍历完，看是否为空串。如果为空串，证明有效，否则无效。

使用一个栈用来存放字符。

遍历字符串，当栈的元素个数大于2并且当前字符为c并且栈顶元素为b时，查看栈中第二个元素是否为a，如果为a，则证明遇到了一个连续的abc，去掉；否则将当前字符入栈。

遍历完成，查看栈是否为空。

算法实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> stack;
        for(char ch : s) {
            if(stack.size() >= 2 && ch == 'c' && stack.top() == 'b') {
                char top = stack.top();
                stack.pop();
                if(stack.top() == 'a') {
                    stack.pop();
                } else {
                    stack.push(top);
                    stack.push(ch);
                }
            } else {
                stack.push(ch);
            }
        }
        return stack.empty();
    }
};

性能分析

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

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

另一种解法

算法思想

其实也不算新的思路。只是做了一些优化。平均的时间复杂度更好一些。

上一个思路使用的是栈，只能访问栈顶元素。可以使用数组，这样所有元素就都可以访问。

并且只要能够判定该字符串一定无效，就直接返回false，而不再继续遍历。

对于访问的字符，有三种情况：

1. a：直接添加到数组中
2. b：查看数组是否为空，如果为空，证明一定无效，返回false
3. c：查看数组长度是否小于2，如果小于2，证明一定无效，返回false。如果大于等于2，判断当前数组末尾元素时是否为b和当前末尾的前一个元素是否为a，只要有一个判断为false，就证明该字符串无效，返回false。如果都正确，就证明这是一个连续的abc，去掉，然后继续遍历。

可以使用top变量表示当前数组末尾的索引。

算法实现

class Solution {
public:
    bool isValid(string s) {
        char array[s.size()];
        int top = -1;
        for(char ch : s) {
            switch (ch) {
                case 'a':
                    array[++top] = 'a';
                    break;
                case 'b':
                    if(top == -1) {
                        return false;
                    }
                    array[++top] = 'b';
                    break;
                case 'c':
                    if(top < 1) {
                        return false;
                    }
                    if(array[top] != 'b' || array[top - 1] != 'a') {
                        return false;
                    }
                    top -= 2;
                    break;
            }
        }
        return top == -1;
    }
};

性能分析

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

空间复杂度：$O(n)$。也可以直接将数组的大小设为字符串长度最大值，这样空间复杂度变为$O(1)$。