题目链接

最长回文子串

题目描述

image.png

实现代码

思路：首先可以知道，对任意从第i个位置到第j个位置的子串s[i][j]，判断其是否为最长回文串的依据可以通过其子串s[i+1][j-1] 及s[i]==s[j]判断出来，同时，我们通过自底向上的形式进行回文串的查找并对起始点和回文串长度进行跟踪记录，最终解出答案；

因此，判断子串是否为回文串可以通过下列状态转移方程进行判断：

dp[i][j] = dp[i+1][j-1] && (s.charAt(i} == s.charAt(j))

同时，需要对边界值进行初始化：

  1. i = j时， dp[i][j] = true
  2. i > j时，dp[i][j] = true；为什么设置为true，是因为通过状态转移方程进行计算时使用的是逻辑与

实现代码：

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3. int len = s.length();
  5.         boolean[][] dp = new boolean[len][len];
  7.         for (int i = 0; i < len; i++) {
  8.             for(int j=0; j<len; j++) {
  9.                 if(i >= j) {
  10.                     dp[i][j] = true;
  11.                 }
  12.             }
  13.         }
  15.         int startIdx = 0;
  16.         int resLen = 1;
  18.         for (int subLen = 2; subLen <= len; subLen++) {
  20.             for (int i = 0; i <= len - subLen; i++) {
  22.                 int j = i + subLen - 1;
  24.                 dp[i][j] = dp[i+1][j-1] && (s.charAt(i) == s.charAt(j));
  26.                 if(dp[i][j] && subLen > resLen) {
  27.                     startIdx = i;
  28.                     resLen = subLen;
  29.                 }
  30.             }
  31.         }
  33.         return s.substring(startIdx, startIdx+resLen);
  34.     }
  35. }