题目描述

给你一个字符串 s，找到 s 中最长的回文子串。leetcode链接

解题思路

方法1

第一种就是遍历每个位置，从当前位置开始向两边检查最大回文串

这个方法需要注意的是：由于回文串的长度可能为奇数或者偶数，所以检查的时候，要考虑两种情况；

• 如果为奇数，当前位置就是中心位置，从两边开始检查，find(i, i)
• 如果为偶数，当前位置只是左边中心，要从当前位置i和下一个位置i+1 开始检查，find(i, i+1)

代码

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() <= 0) return s;
        int maxLen = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = find(s.toCharArray(), i, i);     // 长度为奇数
            int len2 = find(s.toCharArray(), i, i + 1); // 长度为偶数
            int len = Math.max(len1, len2);
            if (len > maxLen) {
                maxLen = len;
                // 0 1 2   i = 1, len = 3, start = 1 - (2/2) = 0
                // 0 1 2 3 i = 1, len = 4, start = 1 - (3/2) = 0
                start = i - (len - 1) / 2;
            }
        }
        // substring(a,b) 是左闭右开
        return s.substring(start, start + maxLen);
    }

    // 从当前位置寻找最长回文串
    private int find(char[] cs, int left, int right) {
        int len = cs.length;
        while (left >= 0 && right < len && cs[left] == cs[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }
}

方法2

• 这个方法用到了动态规划的思想。本题可以使用暴力解法：每遍历到一个位置i，就在区间\([0, i]\)内两边往中间逼近，得到当前区间内的最大回文串。
• 动态规划就是用来优化上述暴力解法，使用 \(dp[i][j]\) 记录边界为i 和 j 时是否为回文串，如果是，那只要 \(cs[i - 1] == cs[j + 1]\)，那么因为内层为回文串且左右边界字符相等
• 因此新的区间 \([i-1, j+1]\) 就构成了更长的回文串

代码

class Solution {
    public String longestPalindrome(String s) {
      if (s == null || s.length() < 2) {
          return s;
      }
      char[] cs = s.toCharArray();
      int maxLen = 1;
      int start = 0;
      boolean[][] dp = new boolean[cs.length][cs.length];
      for (int j = 0; j < cs.length; j++) {
          for (int i = 0; i < j; i++) {
              // 三个字符以内，或者内部为回文串
              if (cs[i] == cs[j] && (j - i <= 2 || dp[i+1][j-1])) {
                  dp[i][j] = true;
                  if (j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    start = i;
                  }
              }
          }
      }  

      return s.substring(start, start + maxLen);
    } 
}