Java 實作回文判斷與字元統計：從演算法到完整程式碼

問題定義

• 回文判斷：字串正反讀相同（如 "aba"、"abba"）。
• 字元頻率統計：計算每個字元出現次數。
• 重組為回文：若可能，將字串重新排列成回文（最多一個奇數次字元置中）。

核心演算法

1. 回文判斷 — 雙指針法

public boolean isPalindrome(String s) {
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s.charAt(i++) != s.charAt(j--)) return false;
    }
    return true;
}

時間 O(n)，空間 O(1)。

2. 字元統計 — HashMap 計數

public Map<Character, Integer> countChars(String s) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) {
        map.merge(c, 1, Integer::sum);
    }
    return map;
}

原始碼使用雙重迴圈（O(n²)），改用 merge 或 compute 可降為 O(n)。

3. 重組回文 — 貪婪填充

1. 統計字元頻率，計算奇數次字元個數（oddCount）。
2. 若 oddCount > 1，無法組成回文，回傳 null。
3. 建立 char[] 或 StringBuilder，雙指針 left、right 從兩端向中間填入成對字元。
4. 若有奇數次字元，填入中間位置。

public String toPalindrome(String s) {
    Map<Character, Integer> freq = countChars(s);
    int odd = 0; char oddChar = 0;
    for (var e : freq.entrySet()) {
        if (e.getValue() % 2 == 1) { odd++; oddChar = e.getKey(); }
    }
    if (odd > 1) return null;

    char[] res = new char[s.length()];
    int l = 0, r = s.length() - 1;
    for (var e : freq.entrySet()) {
        char c = e.getKey(); int cnt = e.getValue();
        if (c == oddChar) continue; // 稍後處理
        for (int i = 0; i < cnt / 2; i++) {
            res[l++] = c; res[r--] = c;
        }
    }
    if (odd == 1) {
        for (int i = 0; i < freq.get(oddChar); i++) res[l++] = oddChar;
    }
    return new String(res);
}

完整可執行類別

import java.util.*;

public class PalindromeTool {
    private final String text;

    public PalindromeTool(String text) { this.text = text; }

    public boolean isPalindrome() { /* 雙指針實作 */ }

    public Map<Character, Integer> countChars() { /* HashMap 統計 */ }

    public String toPalindrome() { /* 重組邏輯 */ }

    public static void main(String[] args) {
        PalindromeTool tool = new PalindromeTool("1122334455667788990");
        System.out.println("是回文？" + tool.isPalindrome());
        System.out.println("字元統計：" + tool.countChars());
        System.out.println("重組結果：" + tool.toPalindrome());
    }
}

效能與改進重點

• 統計階段避免 indexOf + 雙重迴圈，改用單次遍歷 Map.merge。
• 重組使用 StringBuilder（非執行緒安全，效能優於 StringBuffer）。
• 可擴展支援 Unicode 增補字元（codePointAt）。