数组栈、队列和stl习题

牛牛喜欢跟字符串玩耍，他学会了一种新操作：在当前字符串中任意位置（包括开头和结尾）插入子串。牛牛称一个字符串为好串，当且仅当它可以通过若干次上述操作从空串生成。例如， ab、 aabb、 aababb 都是好串，而 aab、 ba、 abbb 不是好串。现给定一个字符串 s，请判断字符串 s 是否是好串。

问题分析

题目定义了一种"好串"：可以通过在空串中任意位置（包括开头和结尾）反复插入子串"ab"生成的字符串。

观察好串的性质：

每次插入"ab"会增加一个'a'和一个'b'
任何前缀中，'a'的数量必须大于等于'b'的数量
整个字符串中，'a'和'b'的数量必须相等
字符串只能包含'a'和'b'两种字符

解法思路

我们可以使用栈来模拟这个过程：

遍历字符串中的每个字符
当遇到字符'a'时，将其压入栈中
当遇到字符'b'时：
- 检查栈是否为空，若为空则说明没有匹配的'a'，不是好串
- 若栈非空，则弹出栈顶的一个'a'，表示匹配成功
遍历完成后，检查栈是否为空：
- 若栈为空，说明所有'a'都找到了匹配的'b'，是好串
- 若栈非空，说明有剩余的'a'没有匹配，不是好串

这种思路类似于括号匹配问题，其中'a'相当于左括号，'b'相当于右括号。

算法步骤

初始化一个空栈
依次遍历字符串中的每个字符：
- 若字符是'a'，压入栈
- 若字符是'b'，检查栈是否为空，若为空返回false，否则弹出栈顶元素
- 若字符既不是'a'也不是'b'，直接返回false
遍历结束后，检查栈是否为空，为空则返回true，否则返回false

代码实现

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        
        stack<char> stk;
        bool isGood = true;
        
        for (char c : s) {
            if (c == 'a') {
                // 遇到'a'，压入栈中等待匹配
                stk.push(c);
            } else if (c == 'b') {
                // 遇到'b'，需要与之前的'a'匹配
                if (stk.empty()) {
                    // 栈为空，没有可匹配的'a'
                    isGood = false;
                    break;
                }
                stk.pop(); // 匹配成功，弹出一个'a'
            } else {
                // 出现非a/b字符，不符合好串定义
                isGood = false;
                break;
            }
        }
        
        // 检查是否还有未匹配的'a'
        if (!stk.empty()) {
            isGood = false;
        }
        
        cout << (isGood ? "Yes" : "No") << '\n';
    }
    
    return 0;
}

示例验证

"ab"：压入'a'，遇到'b'弹出'a'，栈空 → Yes
"aabb"：压入'a'，压入'a'，遇到'b'弹出'a'，遇到'b'弹出'a'，栈空 → Yes
"ba"：遇到'b'时栈空 → No
"aab"：压入'a'，压入'a'，遇到'b'弹出'a'，栈非空 → No
"abbb"：压入'a'，遇到'b'弹出'a'，栈空；再遇到'b'时栈空 → No

复杂度分析

时间复杂度：O(n)，其中n是字符串长度，每个字符只被处理一次
空间复杂度：O(n)，最坏情况下（全是'a'）需要存储所有字符