PAT 甲級 1062 「答案正確」字串判定 Java 完整解法與除錯

題目重述

判斷字串是否符合「答案正確」規則：

1. 僅含 P、A、T 三種字元。
2. 形如 xPATx 者正確，x 為空串或純 A。
3. 若 aPbTc 正確，則 aPbATca 也正確（a,b,c 為空或純 A）。

輸入 n 條字串，逐行輸出 YES/NO。

規律推導

設 P 前有 a 個 A，P~T 間有 b 個 A，T 後有 c 個 A。
規則 2 要求 a == c。
規則 3 要求 c == a * b。
合併得 a == c 且 c == a * b → a == a * b → b == 1 (當 a > 0) 或 a == 0 (任意 b)。

綜合條件：

• 字串僅含 P/A/T。
• 恰好一個 P、一個 T，且 P 在 T 前。
• P 與 T 之間至少一個 A（即 b >= 1）。
• 設 a = countA前, b = countA中, c = countA後，滿足 a * b == c。

正確 Java 實作

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            String s = in.next();
            System.out.println(check(s) ? "YES" : "NO");
        }
    }

    static boolean check(String s) {
        // 1. 字元合法性
        for (char ch : s.toCharArray()) {
            if (ch != 'P' && ch != 'A' && ch != 'T') return false;
        }
        // 2. 單一 P、T 且順序正確
        int p = s.indexOf('P');
        int t = s.indexOf('T');
        if (p == -1 || t == -1 || p >= t || s.indexOf('P', p+1) != -1 || s.indexOf('T', t+1) != -1) 
            return false;
        // 3. 計算三段 A 數量
        int a = 0, b = 0, c = 0;
        for (int i = 0; i < p; i++) if (s.charAt(i) == 'A') a++;
        for (int i = p+1; i < t; i++) if (s.charAt(i) == 'A') b++;
        for (int i = t+1; i < s.length(); i++) if (s.charAt(i) == 'A') c++;
        // 4. 中間至少一個 A
        if (b == 0) return false;
        // 5. 核心規則 a * b == c
        return a * b == c;
    }
}

原始碼常見錯誤分析

測試樣例

輸入：
8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

輸出：
YES
YES
YES
YES
NO
NO
NO
NO

核心洞見：將字串視為 A^a P A^b T A^c，條件化簡為 b>=1 且 a*b==c。避免複雜索引運算，改用計數器直觀且不易出錯。