题目描述

We are given that the string "abc" is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + "abc" + Y is also valid.

If for example S = "abc", then examples of valid strings are: "abc", "aabcbc", "abcabc", "abcabcababcc". Examples of invalid strings are: "abccba", "ab", "cababc", "bac".

Return true if and only if the given string S is valid.

Example 1:

Input: "aabcbc"
Output: true
Explanation: 
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

Note:

1. 1 <= S.length <= 20000
2. S[i] is 'a', 'b', or 'c'

题意：”abc”是合法的，如果一个字符串是合法的，那么把他拆分开来S = X + Y,那么字符串X + "abc" + Y也是合法的。给一个字符串判断其是否合法。

算法1

(栈) $O(n)$

题解：我们可以观察得知最终的字符串一定包含一个"abc"，如果我们从原来的字符串中删除这个"abc"，那么X ,Y便会合在一起，形成一个新的"abc"。因此我们只需要不断的删除字符串"abc"，判断最后剩下来的是否是空串即可。为了能够在$O(n)$的时间复杂度内完成，我使用了栈来进行模拟操作，操作顺序如下：

• 如果读入的字符是a,b直接入栈。
• 否则：
• 如果栈内元素小于2，返回false。
• 如果栈内元素大于2，并且次栈顶元素和栈顶元素分别是a,b。那么将这两个元素出栈，否则将c入栈。

最后判断栈是否为空。

    bool isValid(string s) {
        int n = s.length(),top = 0;
        vector<char> st(n);
        if(n % 3 != 0) return false; 
        for(int i = 0 ; i < n ; i ++)
        {
            if(s[i] == 'c')
            {
                if(top >= 2)
                {
                    if(st[top - 1] == 'b' && st[top - 2] == 'a')
                        top = top - 2;
                    else
                        st[top ++] = 'c';
                }
                else 
                    return false;
            }
            else
                st[top ++] = s[i];
        }
        return top == 0;
    }