题目描述

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

示例1：

  1. 输入：s = "babad"
  2. 输出："bab"
  3. 解释："aba" 同样是符合题意的答案。

示例2：

  1. 输入：s = "cbbd"
  2. 输出："bb"

示例3：

  1. 输入：s = "a"
  2. 输出："a"

思路

动态规划。=> 使用dp[i][j]表示从i到j是否为回文。

如果希望dp[i][j]为回文的话，那么首先字符str[i] == str[j]并且dp[i + 1][j - 1]也是回文。

注意，如果str[i] == str[j] 且i到j一共只有三个字符，那么他们就是回文。

因此，步骤如下：

  1. 初始化dp数组，对角线全为true；
  2. j指向的是后面的字符，因此外循环遍历j，从j = 1开始；
  3. i指向前面的字符，内循环遍历i, 每次都是从i = 0 开始；
  4. 如果str[j] != str[i] 说明从i到j必定不是回文，那么i 往后移动，终止条件为i < j;
  5. 如果str[j] == str[i] 此时有两种情况
  • 只有三个字符，直接设置为true
  • 大于三个字符，那么如果dp[i + 1][j - 1]也为true, 那么dp[i][j]也为true
  1. 当dp[i][j]为true时，判断此时的回文长度，如果大于之前的最大回文长度，那么最后要的索引就更新为i和j，否则不更新。

代码

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.         int len = s.length();
  4.         // 长度为1，已经是回文了
  5.         if (len == 1) {
  6.             return s;
  7.         }
  9.         int start = 0;
  10.         int end = 0;
  11.         int maxLength = 0;
  13.         boolean[][] dp = new boolean[len][len];
  15.         // 初始化
  16.         for (int i = 0; i < len; i++) {
  17.             dp[i][i] = true;
  18.         }
  20.         // 从j开始遍历
  21.         for (int j = 1; j < len; j++) {
  22.             for (int i = 0; i < j; i++) {
  23.                 if (s.charAt(i) != s.charAt(j)) {
  24.                     dp[i][j] = false;
  25.                 } else {
  26.                     if (j - i < 3) {
  27.                         dp[i][j] = true;
  28.                     } else {
  29.                         dp[i][j] = dp[i + 1][j -1];
  30.                     }
  32.                     // 不要漏了dp[i][j]为true这一条件
  33.                     if (dp[i][j] && j - i + 1 > maxLength) {
  34.                         start = i;
  35.                         end = j;
  36.                         maxLength = j - i + 1;
  37.                     }
  39.                 }
  40.             }
  41.         }
  43.         return s.substring(start, end + 1);    
  44.     }
  45. }

注意：

  1. 最大长度的计算方法：j - i + 1，记得要+ 1， 例如i = 0, j = 2， 长度为3，即 2 - 0 + 1；
  2. 只有当dp[i][j]为true时，才去尝试修改最大长度，即
    if (dp[i][j] && j - i + 1 > maxLength) {
 start = i;
 end = j;
 maxLength = j - i + 1;
}

pss: 该题可用“马拉车算法”，将复杂度降到O(n)，但是非常复杂，面试想不出来，因此只用动态规划即可。