当前位置：首页 > news >正文

最长回文子串：动态规划推导

news 来源：原创 2024/9/20 5:14:34

最长回文子串：结合图形推导动态规划

题目介绍

本题可以在力扣找到，题号为5。
给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。
示例 2：

输入：s = “cbbd”
输出：“bb”

提示：

1 <= s.length <= 1000
s 仅由数字和英文字母组成

暴力解法

先从暴力解法入手，对于长度为n的字符串，总共有 (n+1) * n / 2 种组合，我们可以找出每种组合，然后判断其是否是回文串，最后与当前的最大值进行比较，若新串更大，就更新答案。

我们先写一个判断回文串的函数，用双指针判断即可：

    public static boolean isPalindrome(String s) {int left = 0;int right = s.length() - 1;while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}

然后我们用双重循环，遍历到每一种可能，在进行进一步判断：

class Solution {public String longestPalindrome(String s) {String resp = "";int ans = 0;int[][] dp = new int[s.length()][s.length()];int n = s.length();for (int i = 0;i < n;i++) {for (int j = i;j < n;j++) {//获取子串String subString = s.substring(i,j+1);//判断是否要更新最长子串if (subString.length() > resp.length() && isPalindrome(subString)) {resp = subString;}}}//返回答案return resp;}public boolean isPalindrome(String s) {int left = 0;int right = s.length() - 1;while (left < right) {if (s.charAt(left) != s.charAt(right)) {return false;}left++;right--;}return true;}
}

动态规划

接下来我们可以考虑动态规划的解法，所谓动态规划，就是用之前的状态递推后面的状态。首先我们需要确定一个状态转移条件，对于一个字符串来说，如果有一个子串str 为回文串，且 str的前一个字符和后一个字符也相同（比如说 “aba” 和 “aabaa”）那么就说明 [str-1,str+1] 也为回文串。我们可以定一个二维数组，将其定义为从 i 到 j 的子串是否是回文串:

//初始化一个状态数组--布尔类型
int[][] dp = new int[n][n];
for (int i = 0;i < n;i++) {//对于单个字符的情况，必定为回文串dp[i][i] = true;
}

根据我们之前的结论，可以推出状态转移方程，即

if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1] == true) {dp[i][j] = true;
} else {dp[i][j] = false;
}

可以看到，dp[i][j]的状态是基于 dp[i+1][j-1]的，即若要得到 dp[i][j],则要先得到dp[i+1][j-1]的状态，光这么描述其实还是很抽象，我们借助矩阵图来理解：
在这里插入图片描述
我们把横轴作为j，纵轴作为i，首先我们可以填充 dp[i][i],即只有一个字符的情况，都可以填充为true:

其次，对于j > i 的情况其实都可以不用考虑，因为起始位置是要始终小于结束位置的：

接着，我们推到一般情况的依赖关系，我们先任选一点，比如 dp[0][2],根据状态转移方程，我们需要参考的就是 dp[1][1] 的状态值了：
在这里插入图片描述
即，对于每一个状态，在二位图像上总是需要依赖其左下角的具体状态，所以理论上来说，只要从对线向右上填充，我们就可以得到整个dp数组的状态了：

对于上面的示例来说，只要我们填充了 i = j 以及 i + 1 = j 这两条对角线，我们就可以成功推导出整个dp数组的状态，接下来我们开始编程实现：

    public static String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];//填充对角线for (int i = 0;i < n;i++) {dp[i][i] = true;}//填充 j = i + 1for (int i = 0;i < n-1;i++) {int j = i + 1;if (s.charAt(i) == s.charAt(j)) {dp[i][j] = true;}}//填充其余情况,按对角线顺序填充for (int offset = 0;offset < n-2;offset++) {for (int i = 0;i < n-2-offset;i++) {int j = i + 2 + offset;if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {dp[i][j] = true;}}}//遍历dp数组，求出最长值int longestLength = 0;String resp = "";for (int i = 0;i < n;i++) {for (int j = 0;j < n;j++) {if (dp[i][j] && j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}return resp;}

具体实现就如上，需要注意的是，由于 dp[i][j] 依赖于 dp[i+1][j-1],即依赖于左下角的状态，所以我们填充一般状态的时候也需要按照这个顺序填充，即需要按照对角线层层填充才能得到正确答案。

我们可以与暴力做法的耗时作比较，暴力解法耗时大概在 1000ms左右，而上面这种基于动态规划的解法耗时只有 200ms左右：
在这里插入图片描述
大幅优化了耗时，不过上述解法中还有可以改进的地方，比如我们可以在填充dp数组的时候就开始寻找答案，而不是分两步走：

    public static String longestPalindrome(String s) {int n = s.length();boolean[][] dp = new boolean[n][n];//填充对角线for (int i = 0;i < n;i++) {dp[i][i] = true;}int longestLength = 1;String resp = s.charAt(0) + "";//填充 j = i + 1for (int i = 0;i < n-1;i++) {int j = i + 1;if (s.charAt(i) == s.charAt(j)) {dp[i][j] = true;if (j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}//填充其余情况,按对角线顺序填充for (int offset = 0;offset < n-2;offset++) {for (int i = 0;i < n-2-offset;i++) {int j = i + 2 + offset;if (s.charAt(i) == s.charAt(j) && dp[i+1][j-1]) {dp[i][j] = true;//将判断步骤放入填充步骤中if (j - i + 1 > longestLength) {longestLength = j - i + 1;resp = s.substring(i,j+1);}}}}return resp;}