回文子串

一个字符串正着读和反着读结果相同。

误区

求字符串中的最长回文子串，不能将两个字符串进行反转，然后求其公共子串。例如：

原字符串：abctestcba
反转字符串：abctsetcba
公共字串：abc
但是abc却不是回文子串

思路

• 动态规划
  dp[i][j] 表示从i到j的字符串是否是回文字串，已知dp[i][i]=true。
  因此

if (i == j) dp[i][j] = true;
else if (j - i == 1) dp[i][j] = (s.charAt(i) == s.charAt(j));
else dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
if (dp[i][j] && ((j - i + 1) > ans.length())) ans = s.substring(i, j + 1);

• 双指针
  由于字符串的长度可能是奇数也可能是偶数，这个决定了回文字串的长度可能是奇数aba，或者偶数aa的形态。这个方法采用遍历的方式求出最长回文字串。

public String palindrome(String s, int i, int j) {
    while (i >= 0 && j <= s.length() - 1 && s.charAt(i) == s.charAt(j)) {
        i--;
        j++;
    }
    return s.substring(i + 1, j);
}