字符串回文题（最长回文子串 · 验证回文 · 回文数）

验证回文串（LeetCode 125）

只考虑字母和数字，忽略大小写：

boolean isPalindrome(String s) {
    int l = 0, r = s.length() - 1;
    while (l < r) {
        while (l < r && !Character.isLetterOrDigit(s.charAt(l))) l++;
        while (l < r && !Character.isLetterOrDigit(s.charAt(r))) r--;
        if (Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r)))
            return false;
        l++; r--;
    }
    return true;
}

回文数（LeetCode 9）

不借助字符串，反转后半部分数字：

boolean isPalindromeNum(int x) {
    if (x < 0 || (x % 10 == 0 && x != 0)) return false;
    int rev = 0;
    while (x > rev) {
        rev = rev * 10 + x % 10;
        x /= 10;
    }
    return x == rev || x == rev / 10;  // 奇数位时 rev 多一位
}

最长回文子串（LeetCode 5）

中心扩展法（推荐，O(n²)）

String longestPalindrome(String s) {
    int start = 0, maxLen = 1;
    for (int i = 0; i < s.length(); i++) {
        // 奇数长度（以 i 为中心）
        int len1 = expandAround(s, i, i);
        // 偶数长度（以 i, i+1 为中心）
        int len2 = expandAround(s, i, i + 1);
        int len = Math.max(len1, len2);
        if (len > maxLen) {
            maxLen = len;
            start = i - (len - 1) / 2;
        }
    }
    return s.substring(start, start + maxLen);
}

private int expandAround(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
    return r - l - 1;
}

DP 解法（O(n²)）

dp[i][j] = s[i..j] 是否是回文。

String longestPalindromeDP(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int start = 0, maxLen = 1;
    for (int i = 0; i < n; i++) dp[i][i] = true;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = (len == 2) || dp[i + 1][j - 1];
                if (dp[i][j] && len > maxLen) { maxLen = len; start = i; }
            }
        }
    }
    return s.substring(start, start + maxLen);
}

Manacher 算法（O(n)）

预处理字符串加 # 号，统一奇偶，用已计算结果加速：

String manacher(String s) {
    // 转换：abc → #a#b#c#
    StringBuilder sb = new StringBuilder("#");
    for (char c : s.toCharArray()) { sb.append(c); sb.append('#'); }
    String t = sb.toString();
    int n = t.length();
    int[] p = new int[n];  // p[i] = 以 i 为中心的回文半径
    int center = 0, right = 0;
    int maxLen = 0, maxCenter = 0;
    for (int i = 0; i < n; i++) {
        if (i < right) p[i] = Math.min(right - i, p[2 * center - i]);
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n
               && t.charAt(i - p[i] - 1) == t.charAt(i + p[i] + 1)) p[i]++;
        if (i + p[i] > right) { center = i; right = i + p[i]; }
        if (p[i] > maxLen) { maxLen = p[i]; maxCenter = i; }
    }
    return s.substring((maxCenter - maxLen) / 2, (maxCenter + maxLen) / 2);
}

最长回文子序列（LeetCode 516）

子序列不要求连续，区间 DP：

int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i + 1][j - 1] + 2;
            else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
        }
    }
    return dp[0][n - 1];
}