您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 回文字符串判斷與構造算法完整實現

編輯：Java 相關知識

問題定義

判斷：給定字符串，檢查是否正反讀取相同
構造：給定字符串，重新排列字符構造回文串（若可能）

核心算法邏輯

1. 回文判斷 — 雙指針 O(n)

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

2. 字符頻統計 — HashMap O(n)

public Map<Character, Integer> countChars(String text) {
    Map<Character, Integer> map = new HashMap<>();
    StringBuilder unique = new StringBuilder();
    
    // 去重收集字符
    for (int i = 0; i < text.length(); i++) {
        char c = text.charAt(i);
        if (unique.indexOf(String.valueOf(c)) < 0) {
            unique.append(c);
        }
    }
    
    // 統計每字符出現次數
    for (int i = 0; i < unique.length(); i++) {
        char c = unique.charAt(i);
        int count = 0;
        for (int j = 0; j < text.length(); j++) {
            if (text.charAt(j) == c) count++;
        }
        map.put(c, count);
    }
    return map;
}

3. 回文構造 — 貪心填充 O(n)

public String constructPalindrome(String text) {
    Map<Character, Integer> freq = countChars(text);
    int total = text.length();
    int oddCount = 0;
    Character oddChar = null;
    
    // 檢查可行性：至多一個奇數次字符
    for (int count : freq.values()) {
        if (count % 2 != 0) {
            oddCount++;
            oddChar = freq.entrySet().stream()
                .filter(e -> e.getValue() % 2 != 0)
                .findFirst().get().getKey();
        }
    }
    if (oddCount > 1) return null;  // 無法構造
    
    // 雙端填充
    StringBuilder sb = new StringBuilder(text);
    int left = 0, right = total - 1;
    
    for (Map.Entry<Character, Integer> e : freq.entrySet()) {
        char c = e.getKey();
        int cnt = e.getValue();
        
        if (cnt % 2 == 0) {
            // 偶數次：對稱填充
            for (int i = 0; i < cnt / 2; i++) {
                sb.setCharAt(left++, c);
                sb.setCharAt(right--, c);
            }
        } else {
            // 奇數次：留中間填充
            oddChar = c;
        }
    }
    
    // 填充中間字符（若有）
    if (oddChar != null) {
        for (int i = 0; i < freq.get(oddChar); i++) {
            sb.setCharAt(left++, oddChar);
        }
    }
    
    return sb.toString();
}

完整可運行類

package com.gdh.backtext;

import java.util.*;

public class BackText {
    private String text;
    
    public BackText(String text) { this.text = text; }
    
    public boolean isBackText() {
        for (int i = 0, j = text.length() - 1; i <= j; i++, j--) {
            if (text.charAt(i) != text.charAt(j)) return false;
        }
        return true;
    }
    
    public Map<Character, Integer> countString() {
        Map<Character, Integer> map = new HashMap<>();
        StringBuilder unique = new StringBuilder();
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (unique.indexOf(String.valueOf(c)) < 0) unique.append(c);
        }
        for (int i = 0; i < unique.length(); i++) {
            char c = unique.charAt(i);
            int count = 0;
            for (int j = 0; j < text.length(); j++) {
                if (text.charAt(j) == c) count++;
            }
            map.put(c, count);
        }
        return map;
    }
    
    public String convert() {
        Map<Character, Integer> map = countString();
        int total = text.length();
        int oddCount = 0;
        Character oddChar = null;
        
        for (int cnt : map.values()) {
            if (cnt % 2 != 0) { oddCount++; oddChar = map.entrySet().stream()
                .filter(e -> e.getValue() % 2 != 0).findFirst().get().getKey(); }
        }
        if (oddCount > 1) { System.out.println("無法構造回文"); return null; }
        
        StringBuilder sb = new StringBuilder(text);
        int left = 0, right = total - 1;
        
        for (Map.Entry<Character, Integer> e : map.entrySet()) {
            char c = e.getKey(); int cnt = e.getValue();
            if (cnt % 2 == 0) {
                for (int i = 0; i < cnt / 2; i++) {
                    sb.setCharAt(left++, c); sb.setCharAt(right--, c);
                }
            }
        }
        if (oddChar != null) {
            for (int i = 0; i < map.get(oddChar); i++) sb.setCharAt(left++, oddChar);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        BackText bt = new BackText("1122334455667788990");
        System.out.println(bt.isBackText() ? "是回文" : "非回文");
        System.out.println("構造結果：" + bt.convert());
    }
}

複雜度分析

操作	時間複雜度	空間複雜度
判斷回文	O(n)	O(1)
字符統計	O(n²) 可優化為 O(n)	O(k) k=字符種類
構造回文	O(n)	O(n)

優化建議

統計階段用 map.merge(c, 1, Integer::sum) 單次遍歷 O(n)
構造階段用 char[] 避免 StringBuilder setCharAt 開銷
大數據量考慮流式處理

測試用例

Input:  "1122334455667788990"  // 每數字2次 + 0一次
Output: "1234567890987654321"  // 可構造

Input:  "abc"
Output: null  // 三個奇數次，不可構造

Input:  "racecar"
Output: "racecar"  // 本身即回文