LeetCode [5] 最长回文子串

  题目：最长回文子串

Category Difficulty Likes Dislikes algorithms Medium (31.73%) 2630 - Tags string | dynamic-programming Companies 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb"

方法一：暴力匹配 （Brute Force）

根据回文子串的定义，枚举所有长度大于等于 22 的子串，依次判断它们是否是回文；在具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”；在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。 public class Solution { public String longestPalindrome(String s) { int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组 char[] charArray = s.toCharArray(); // 枚举所有长度大于 1 的子串 charArray[i..j] for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); } /** * 验证子串 s[left..right] 是否为回文串 */ private boolean validPalindromic(char[] charArray, int left, int right) { while (left < right) { if (charArray[left] != charArray[right]) { return false; } left++; right--; } return true; } }

复杂度分析：

时间复杂度：O(N^3)，这里 N 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，这三种操作都与 N 相关；空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。

 

方法二、动态规划

首先第一步，我们需要定义dp数组的含义，定义二维布尔数组dp[i][j]dp[i][j]数组表示：

字符串s[i⋯j]是否为回文子串，如果是，dp[i][j] = true，如果不是，dp[i][j] = false。

如果我们现在已经知道了dp[i+1][j-1]了，那我们如何计算dp[i][j]呢？通过观察，我们发现：

如果s[i] == s[j]那么说明只要dp[i+1][j-1]是回文子串，那么是dp[i][j]也就是回文子串如果s[i] ！=s [j]那么说明dp[i][j]必定不是回文子串。 if(s.charAt(i) == s.charAt(j)){ dp[i][j] = dp[i+1][j-1] }else{ dp[i][j] = false; }

接下来我们需要考虑base case，这里显而易见，当只有一个字母的时候肯定是回文子串，所以初始化的dp表应该如下图所示。

for(int i = s.length()-1; i>=0; i--){ for(int j = i+1; j<s.length(); j++){ if(s.charAt(i) == s.charAt(j)){ dp[i][j] = dp[i+1][j-1] } else{ dp[i][j] = false; } } }

这样就基本完成了这道题目。但是这样会有一种情况通过不了例如给的例子中的“cbbd”

这道题中的回文子串应该为**“bb”**但是我们的dp表中并没有计算出来，这是因为当计算dp[i][j]的时候，中间已经没有dp[i+1][j-1]了，这是我们在base case中没有考虑到的。由于我们在dp表中表示不出来，那我们就在计算的时候单独拿出来这种情况计算，即i和j相邻的时候:

for(int i = s.length()-1; i>=0; i--){ for(int j = i+1; j<s.length(); j++){ if(s.charAt(i) == s.charAt(j)){ //i和j相邻的时候 if(j - i == 1){ dp[i][j] = true; } else{ dp[i][j] = dp[i+1][j-1] } } else{ dp[i][j] = false; } } }

由于最终需要输出最长的回文子串，我们在遍历的时候记录一下即可。

import java.util.Arrays; class Solution { public String longestPalindrome(String s) { if(s == null || s.equals("")){ return s; } boolean[][] dp = new boolean[s.length()][s.length()]; int[] result = new int[2]; for(int i = 0; i<s.length(); i++) dp[i][i] = true; for(int i = s.length()-1; i>=0; i--){ for(int j = i+1; j<s.length(); j++){ if(s.charAt(i) == s.charAt(j)) { if(j-i == 1){ dp[i][j] = true; } else{ dp[i][j] = dp[i+1][j-1]; } }else{ dp[i][j] = false; } if(dp[i][j]){ if(result[1]-result[0] <= j - i){ result[0] = i; result[1] = j; } } } } return s.substring(result[0],result[1]+1); } }

作者：Geralt_U 链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/5-zui-chang-hui-wen-zi-chuan-dong-tai-gui-hua-jie-/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。