Java 尋找字串中最長回文子串的演算法實作與優化

問題描述

給定一個字串，找出其中最長的回文子串。回文是指正著讀與反著讀都相同的字串，例如 "madam"、"racecar" 或中文的 "上海自來水來自海上"。

判斷單一字串是否為回文

方法一：雙指針法（推薦，O(n) 時間，O(1) 空間）

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

方法二：反轉字串比較（O(n) 時間，O(n) 空間）

private String reverse(String str) {
    StringBuilder sb = new StringBuilder(str);
    return sb.reverse().toString();
}
public boolean isPalindrome2(String s) {
    return s.equals(reverse(s));
}

尋找最長回文子串

暴力解法：枚舉所有子串（O(n³) 時間）

雙重迴圈枚舉所有子串，對每個子串呼叫 isPalindrome 判斷，記錄最長者。適合字串長度較小（< 100）的情況。

中心擴展法（推薦，O(n²) 時間，O(1) 空間）

觀察回文特性：以某字元或兩字元間隙為中心，向兩側擴展。遍歷每個可能的中心（共 2n-1 個），擴展並更新最長回文。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 2) return s;
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        // 奇數長度：以 i 為中心
        expand(s, i, i, start, maxLen);
        // 偶數長度：以 i, i+1 為中心
        expand(s, i, i + 1, start, maxLen);
    }
    return s.substring(start, start + maxLen);
}

private void expand(String s, int left, int right, int[] start, int[] maxLen) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--; right++;
    }
    // 實際回文範圍為 (left+1) 到 (right-1)
    int len = right - left - 1;
    if (len > maxLen[0]) {
        maxLen[0] = len;
        start[0] = left + 1;
    }
}

Manacher 演算法（進階，O(n) 時間）

利用回文對稱性避免重複比較，可在線性時間內解決。適合極長字串（> 10⁴）或競賽程式設計。實作較複雜，此處不贅述，有興趣可自行搜尋。

完整可執行範例

public class LongestPalindromeDemo {
    public static void main(String[] args) {
        String input = "babad"; // 預期輸出 "bab" 或 "aba"
        System.out.println("最長回文子串: " + longestPalindrome(input));
    }
    // ... 請填入上述 longestPalindrome 與 expand 方法
}

效能比較與選型建議

常見陷阱

• 空字串或長度為 1 的字串直接返回本身。
• 中心擴展時注意邊界條件：left >= 0 && right < len。
• 若有多個相同長度的最長回文，題目通常接受任意一個；若需最左或最右，需在更新邏輯中加入 tie-breaker。