首页 > 试题广场 >

好串

[编程题]好串
  • 热度指数:8847 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}牛牛喜欢跟字符串玩耍,他学会了一种新操作:在当前字符串中任意位置(包括开头和结尾)插入子串 \texttt{ab}

\hspace{15pt}牛牛称一个字符串为 好串,当且仅当它可以通过若干次上述操作从 空串 生成。

\hspace{15pt}例如,\texttt{ab}\texttt{aabb}\texttt{aababb} 都是好串,而 \texttt{aab}\texttt{ba}\texttt{abbb} 不是好串。

\hspace{15pt}现给定一个字符串 s,请判断字符串 s 是否是好串。

输入描述:
\hspace{15pt}在一行中输入一个仅由小写字母组成字符串 s1 \leqq |s| \leqq 10^5)。


输出描述:
\hspace{15pt}如果字符串 s 是好串,输出 \texttt{Good};否则输出 \texttt{Bad}
示例1

输入

ab

输出

Good

说明

初始空串,插入一次 "ab" 即可得到 "ab"。
示例2

输入

aab

输出

Bad

说明

无法通过插入 "ab" 操作得到 "aab"。
示例3

输入

abaababababbaabbaaaabaababaabbabaaabbbbbbbb

输出

Bad

备注:

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Deque<Character> stack = new ArrayDeque<>();
        String s = in.next();
        stack.push('1');//防止'b'先手,导致误判
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'a' ) {
                stack.push(s.charAt(i));
                continue;
            }
            if (s.charAt(i) == 'b' && !stack.isEmpty()) {
                char c = stack.pop();
                if (c != 'a') {
                    System.out.println("Bad");
                    return;
                }
                continue;
            }
        }
        stack.pop();//清除加入'1'带来的影响
        if (!stack.isEmpty())
            System.out.println("Bad");
        else System.out.println("Good");
    }
}
发表于 2026-02-02 19:53:31 回复(0)
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();

        boolean result = goodString(str);
        if (result) System.out.print("Good");
        else System.out.print("Bad");
    }

    public static boolean goodString(String str) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (c == 'a') stack.push(c);
            else if (c == 'b') {
                // 当 Stack 为空时调用 pop() 方法,不会返回任何值,而是会直接抛出空栈异常
                if (stack.isEmpty()) return false;
                if (stack.pop() == 'b') return false;
            }
        }
        return stack.isEmpty();
    }
}

发表于 2025-07-31 17:03:58 回复(0)
import java.util.Deque;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String a = in.nextLine();
            char[] str = a.toCharArray();
            Deque<Character> stack = new ArrayDeque<>();
            Boolean good = true;
            for(char m:str){
                if(m == 'a'){//如果元素为a,入栈
                        stack.push(m);
                }else if(m == 'b'){//如果元素为b,若栈空,则返回错误并结束循环;否则弹出栈顶元素
                    if(stack.isEmpty()){
                        good = false;
                        break;
                    }else{
                        stack.pop();
                    }
                }
            }
            good = good && stack.isEmpty()?true:false;
            System.out.println(good ? "Good" : "Bad");
        }
    }
}
发表于 2025-07-10 21:33:04 回复(0)

问题信息

上传者:牛客301599号
难度:
3条回答 1102浏览

热门推荐

通过挑战的用户

查看代码
好串