题目链接

好串

题目描述

牛牛定义了一种"好串"：

  1. 空字符串是好串。
  2. 一个字符串是好串，当且仅当它能由一个好串在任意位置插入一个 "ab" 子串得到。

给定一个只包含小写字母的字符串 s，请判断它是否是好串。

输入格式 一个字符串 s。

输出格式 如果 s 是好串，输出 "Good"；否则输出 "Bad"。

示例

  • 输入: aababb
  • 输出: Good (可以这样生成: "" -> "ab" -> "a(ab)b" -> "aabb" -> "a(ab)abb" -> "aababb")
  • 输入: aab
  • 输出: Bad

解题思路

这道题看似复杂，但其核心结构与经典的"括号匹配"问题同源。我们可以逆向思考这个问题：如果一个字符串可以通过不断插入 "ab" 得到，那么它也应该可以通过不断消除 "ab" 这个子串最终变为空字符串。

方法一：循环替换 (效率较低) 一个直观的想法是循环查找并删除字符串中的 "ab"：

while "ab" in s:
    s = s.replace("ab", "", 1)
if s == "":
    # 是好串
else:
    # 不是好串

但这个方法效率很低。每次 find 和 replace 操作都需要 O(L) 的时间，总共有约 O(L) 次替换，导致总时间复杂度达到 O(L²)，对于长度为 10⁵ 的字符串来说会超时。

方法二：栈 (高效的 O(L) 解法) 我们可以把这个问题看作一个匹配问题：'a' 是等待匹配的"左括号"，'b' 是前来匹配的"右括号"。一个 'b' 必须匹配离它最近的那个尚未配对的 'a'。栈的"后进先出"特性完美地模拟了这一过程。

算法步骤：

  1. 初始化一个空栈。这个栈用来存储所有我们遇到的、尚未被匹配的 'a'。

  2. 遍历输入字符串 s 中的每一个字符 c。

  3. 根据字符 c 的类型进行判断：

    • 如果 c 是 'a'，我们将其视为一个待匹配的字符，压入栈中。
    • 如果 c 是 'b'，这表示一个匹配机会来了。
      • 我们检查栈是否为空。如果栈是空的，意味着这个 'b' 前面没有可供匹配的 'a'，这不符合"好串"的结构。因此，字符串 s 不可能是好串，可以直接判定为 "Bad"。
      • 如果栈不为空，说明有 'a' 在等待匹配。我们从栈中弹出一个 'a'，表示这对 "ab" 成功匹配并"消除"。
    • 如果 c 不是 'a' 也不是 'b'，根据定义，好串只能由 'a' 和 'b' 构成，因此直接判定为 "Bad"。

  4. 最终检查：当遍历完整个字符串后，检查栈的状态。

    • 如果栈是空的，说明每一个 'a' 都找到了与之匹配的 'b'，整个字符串被完全"约简"。s 是好串，输出 "Good"。
    • 如果栈不为空，说明有多余的 'a' 没有被匹配，s 不是好串，输出 "Bad"。

这个 O(L) 的算法可以高效地解决本题。

代码

#include <iostream>
#include <string>
#include <stack>

using namespace std;

int main() {

    string s;
    cin >> s;

    stack<char> st;
    for (char c : s) {
        if (c == 'a') {
            st.push(c);
        } else if (c == 'b') {
            if (st.empty()) {
                cout << "Bad" << endl;
                return 0;
            }
            st.pop();
        } else {
            cout << "Bad" << endl;
            return 0;
        }
    }

    if (st.empty()) {
        cout << "Good" << endl;
    } else {
        cout << "Bad" << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char c : s.toCharArray()) {
            if (c == 'a') {
                stack.push(c);
            } else if (c == 'b') {
                if (stack.isEmpty()) {
                    System.out.println("Bad");
                    sc.close();
                    return;
                }
                stack.pop();
            } else {
                 System.out.println("Bad");
                 sc.close();
                 return;
            }
        }
        
        if (stack.isEmpty()) {
            System.out.println("Good");
        } else {
            System.out.println("Bad");
        }
        
    }
}

def main():
    s = input()
    stack = []
    
    for char in s:
        if char == 'a':
            stack.append(char)
        elif char == 'b':
            if not stack:
                print("Bad")
                return
            stack.pop()
        else:
            print("Bad")
            return
            
    if not stack:
        print("Good")
    else:
        print("Bad")

if __name__ == "__main__":
    main()

算法及复杂度

  • 算法: 基于栈的线性扫描。
  • 时间复杂度: ，其中 L 是输入字符串的长度。我们只对字符串进行一次遍历。
  • 空间复杂度: 。在最坏情况下（例如，字符串全由 'a' 组成），栈的大小将与输入字符串的长度相同。