leetcode 1003

题目：

给你一个字符串s，请你判断它是否有效。字符串s有效需要满足：假设开始有一个空字符串t=””，你可以执行任意次下述操作将t转换为s：
将字符串 “abc” 插入到 t 中的任意位置。形式上，t 变为$t_{left} + “abc” + t_{right}$，其中 $t == t_{left} + t_{right}$ 。注意，$t_{right}$和$t_{left}$ 可能为空 。如果字符串 s 有效，则返回 true；否则，返回 false。

输入输出

示例1：

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

示例2:

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

示例3:

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

提示：

• 1 <= s.length <= $2 \times 10^4$
• s 由字母 ‘a’、’b’ 和 ‘c’ 组成

思路

一次遍历使用一个栈
当遇到字符a时,直接入栈
当遇到字符b时，检查栈顶是否为字符a ,如果是将b入栈，如果不是返回false；
当遇到字符c时，检查栈顶是否为字符b,如果是将c入栈,（再将栈顶的cba弹出）如果不是返回false
最后判断栈是否为空即可

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        int n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == 'b' && (st.empty() || (!st.empty() && st.top() != 'a')))
                return false;
            else if (s[i] == 'c' && (st.empty() || (!st.empty() && st.top() != 'b')))
                return false;
            st.push(s[i]);
            if (s[i] == 'c')
            {
                st.pop();
                st.pop();
                st.pop();
            }
        }
        return st.empty();
    }
};