LeetCode 125. 驗證回文串 - 雙指針原地判斷完整解析

題目要求

給定字符串 s，僅考慮字母數字字符、忽略大小寫，判斷是否為回文。空串視為合法回文。

雙指針算法 O(N) 時間 O(1) 空間

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

關鍵點解析

1. 原地處理：不創建新字符串，直接在原串上雙指針移動，空間 O(1)。
2. 字符合法性判斷：Character.isLetterOrDigit() 同時檢查字母和數字，比手寫 ASCII 範圍更健壯。
3. 大小寫統一：toLowerCase() 逐字符轉換，避免整串轉換的額外空間。
4. 指針移動邏輯：非法字符直接跳過（continue），合法字符比較後雙向收攏。

對比：預處理法（易懂但費空間）

String filtered = s.chars()
    .filter(Character::isLetterOrDigit)
    .mapToObj(c -> String.valueOf((char)Character.toLowerCase(c)))
    .collect(Collectors.joining());
return filtered.equals(new StringBuilder(filtered).reverse().toString());

✅ 代碼簡潔 ❌ O(N) 額外空間，面試中常被追問「能否 O(1) 空間」。

測試用例覆蓋

擴展：Unicode 支持

Java char 只能處理 BMP 字符（U+0000~U+FFFF）。若輸入含 Emoji（輔助平面），需用 codePointAt/codePointBefore 處理代碼點，邏輯相同但指針移動變為 left += Character.charCount(cp)。