本文主要是介绍算法43：动态规划专练（最长回文子串 力扣5题）---范围模型，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之前写过一篇最长回文子序列的博客算法27：最长回文子序列长度（力扣516题）——样本模型 + 范围模型-CSDN博客
在那一篇博客中，回文是可以删除某些字符串组成的。比如：
字符串为：a1b3c4fdcdba， 那么最长回文子序列就是 abccba。长度为6。
本题为力扣第5题：最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
解释一下，如果字符串为 abc121dmcba. 那么最长回文子序列为 abc121cba. 而最长回文子串则为：121. 子串必须是连续的。
一眼看上去就是范围模型。而范围模型就是要讨论样本数据的开头和结尾的情况：
1. 如果字符串为空，那么回文为空字符
2. 如果字符长度为1， 回文子串就为字符串本身
3. 如果字符串长度2， 则字符串下标0和1的字符进行比较，相等则为字符串本身；不等的话，返回其中一个字符即可。这是我在提交代码的时候，力扣提示错误的时候发现的。
为什么要单独讨论长度为 1 和 2 的情况？
因为, 范围模型讨论数据的开头和结尾。如果原始字符串长度为2，则直接走上方的3逻辑； 可如果一个很长的字符串，经过不断的递归以后，最终长度为2的时候，这就比较麻烦了。
比如 *******ab****的时候，你就不能随意返回一个字符作为回文了。
如果你返回a, 那么字符串为mnfabbbbbbbbb. 那你肯定是错误的
如果你返回b，那么字符串为mnfaaaaaaaaabb， 那你肯定也是错的。
回文，就是整体与子串的关系
其实，最长回文子串，最难的就是连续子串的判断。
| 0 | 1 | 2 | 3 | 4 | 5 |
| a | c | d | d | c | k |
字符串为 acddck, 下标1和下标4相等，都为c. 如果下标从1到4 是回文。 那么他的子串
下标2到3也必须是回文才行。这才是判断的核心点。 而下方的推导表格，完全符合。
比如这个字符串为abdddfm。那么二维表格为：
我用x代表空字符串
| a (0) | b (1) | d (2) | d (3) | d (4) | f (5) | m (6) | |
| a (0) | a | X | |||||
| b (1) | b | X | |||||
| d (2) | d | dd | |||||
| d (3) | d | dd | |||||
| d (4) | d | X | |||||
| f (5) | f | X | |||||
| m (6) | m |
由下往上，由左往右推算：
我用x代表空字符串
| a (0) | b (1) | d (2) | d (3) | d (4) | f (5) | m (6) | |
| a (0) | a | X | d | 类推 | 类推 | 类推 | 类推 |
| b (1) | b | X | 类推 | 类推 | 类推 | ||
| d (2) | d | dd |
前dd, 左下d， 下为dd 当前下标与下标2的字符相等。下标 2到4的子串为 3到3。 而3行3列是回文并且回文为d。 那么 d + d + d = ddd | 类推 | 类推 | ||
| d (3) | d | dd | 前dd, 左下d， 下为空字符 f不等于下标3的d。 取最长的 dd | 类推 | |||
| d (4) | d | X | X | ||||
| f (5) | f | X | |||||
| m (6) | m |
最终的二维表就是
| a (0) | b (1) | d (2) | d (3) | d (4) | f (5) | m (6) | |
| a (0) | a | X | b | dd | ddd | ddd | ddd |
| b (1) | b | X | dd | ddd | ddd | ddd | |
| d (2) | d | dd | ddd | ddd | ddd | ||
| d (3) | d | dd | dd | dd | |||
| d (4) | d | X | X | ||||
| f (5) | f | X | |||||
| m (6) | m |
直观的看，最长回文字符就是 ddd.
下面贴出递归代码：
package code04.动态规划专项训练03;/*** 力扣 5 题 ： 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01 {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() == 2) {return s.charAt(0) == s.charAt(1) ? s : String.valueOf(s.charAt(0));}char[] ss = s.toCharArray();return help(ss, 0, ss.length -1);}//样本对应模型: 就是从后往前讨论样本数据的末尾下标无限可能。此处的末尾下标应该为0；public String help(char[] ss, int index1, int index2){//只有一个字符if (index1 == index2) {return String.valueOf(ss[index1]);}//两个字符if (index1 == index2 - 1) {String temp = "";if (ss[index1] == ss[index2]) {temp = String.valueOf(ss[index1]) + String.valueOf(ss[index2]);}return temp;}//index2不作为结尾，index作为开头String p1 = help(ss, index1, index2 - 1);//index2作为结尾，index1不作为开头String p2 = help(ss, index1 + 1, index2);//index2不作为结尾，index1 不作为开头String p3 = help(ss, index1 + 1, index2 - 1);//index2作为结尾， index1 作为开头String p4 = ss[index1] == ss[index2] ? help(ss, index1 + 1, index2 - 1) : "";if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {p4 = String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);}String result = p1.length() > p2.length() ? p1 : p2;result = result.length() > p3.length() ? result : p3;result = result.length() > p4.length() ? result : p4;return result;}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";//String s= "cbbd";//String s= "abdka";String s= "aacabdkacaa";LongestPalindrome_01 ss = new LongestPalindrome_01();System.out.println(ss.longestPalindrome(s));}
}
动态规划：
package code04.动态规划专项训练03;/*** 力扣 5 题 ： 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01_opt {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() == 2) {return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);}char[] ss = s.toCharArray();int size = ss.length;//二维动态规划表，列数多构建1String[][] dp = new String[size][size];//构建dp的斜线for (int i = 0; i < s.length() - 1; i++) {//只构建斜线上方部分. 由递归的if (index1 == index2) 得到dp[i][i] = String.valueOf(ss[i]);//由递归的if (index1 == index2 - 1)得到。递归中还特出判断了length == 2 即原始数组长度为2的//情况。但是，动态规划中原始数组长度为2在上方代码已经判断过了。因此，此处只需要关注通用逻辑即可dp[i][i+1] = ss[i] == ss[i + 1] ? String.valueOf(ss[i]) + String.valueOf(ss[i+1]) : "";}//最后一行最后一列比较特殊，会出现数组越界，因此单独构造dp[size - 1][size - 1] = String.valueOf(ss[size - 1]);//行，从倒数第3行开始，由下放上推； 因为倒数第1、2行上方代码已经推算出来了for (int index1 = size - 3; index1 >= 0; index1--) {//列，由左往右推。 这个地方的 index2 = index1 + 2需要看图理解for (int index2 = index1 + 2; index2 < size; index2++) {//index2不作为结尾，index作为开头String p1 = dp[index1][index2 - 1];//index2作为结尾，index1不作为开头String p2 = dp[index1 + 1][index2];//index2不作为结尾，index1 不作为开头String p3 = dp[index1 + 1][index2 - 1] != null ? dp[index1 + 1][index2 - 1] : "";//index2作为结尾， index1 作为开头String p4 = ss[index1] == ss[index2] ? dp[index1 + 1][index2 - 1] : "";//特殊处理一下p4为null的情况p4 = p4 == null ? "" : p4;if (!"".equals(p4) && (index2 - index1 - 1) == p4.length()) {p4 = String.valueOf(ss[index1]) + p4 + String.valueOf(ss[index2]);}String result = p1.length() > p2.length() ? p1 : p2;result = result.length() > p3.length() ? result : p3;result = result.length() > p4.length() ? result : p4;dp[index1][index2] = result;}}return dp[0][size -1];}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";//String s= "cbbd";//String s= "abdka";String s= "aacabdkacaa";//String s= "abbcccbbbcaaccbababcbcabca";LongestPalindrome_01_opt ss = new LongestPalindrome_01_opt();System.out.println(ss.longestPalindrome(s));}
}
测试结果：
测试结果很不理想。速度慢，而且还吃内存，吃内存的主要原因就是动态规划的二维表是字符串类型的。
看了看力扣官方的思想，确实相当不错。下面直接说一下官方的解题思路。
1. 官方并不存储字符串，而是存一个flag，标记回文范围.
| a (0) | b (1) | d (2) | d (3) | d (4) | f (5) | m (6) | |
| a (0) | true | false | |||||
| b (1) | true | false | |||||
| d (2) | true | true | |||||
| d (3) | true | true | |||||
| d (4) | true | false | |||||
| f (5) | true | false | |||||
| m (6) | true |
力扣官方定义了一个最长回文子串的开始位置，beginIndex，长度length
从倒数第3行开始，依旧是由下往上，由左往右推算
| a (0) | b (1) | d (2) | d (3) | d (4) | f (5) | m (6) | |
| a (0) | true | false | false | false | false | false | false |
| b (1) | true | false | false | false | false | false | |
| d (2) | true | true | d == d，并且 子串 3行3列也是回文 整体是回文。 开始位置为2， 长度为3 | false | false | ||
| d (3) | true | true | d != f false | m != d false | |||
| d (4) | true | false | d ！= m false | ||||
| f (5) | true | false | |||||
| m (6) | true |
最后，就是根据上方的推算结果进行字符串截图。知道了开始位置，截取字符的长度，问题自然就解决了。
代码如下：
package code04.动态规划专项训练03;/*** 力扣 5 题 ： 最长回文子串* https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=dynamic-programming*/
public class LongestPalindrome_01_opt2_1 {public String longestPalindrome(String s) {if (s == null || s.isEmpty()) {return "";}if (s.length() == 1) {return s;}if (s.length() == 2) {return s.charAt(0) == s.charAt(1) ? s : s.substring(0,1);}char[] ss = s.toCharArray();int size = ss.length;//默认开始下标为最后一行的最后一列int beginIndex = size -1;//默认回文长度为1int length = 1;//二维动态规划表，列数多构建1boolean[][] dp = new boolean[size][size];//构建dp的斜线for (int i = 0; i < s.length(); i++) {//只构建斜线上方部分. 由递归的if (index1 == index2) 得到dp[i][i] = true;}//行，从倒数第2行开始，由下放上推； 因为倒数第1行上方代码已经推算出来了for (int index1 = size - 2; index1 >= 0; index1--) {//列，由左往右推。 当前行的剩余列for (int index2 = index1 + 1; index2 < size; index2++) {//长度为2. 开头、结尾相等就是回文if (index1 == index2 - 1) {//开头、结尾相等。那么 [index1, index2] 就是回文dp[index1][index2] = ss[index1] == ss[index2] ? true : false;}else {dp[index1][index2] = ss[index1] == ss[index2] ? dp[index1 + 1][index2 -1] : false;}// [index1, index2] 的个数就是 index2 - index1 + 1；if( dp[index1][index2] && index2 - index1 + 1 > length) {beginIndex = index1;length = index2 - index1 + 1;}}}return s.substring(beginIndex, beginIndex + length);}public static void main(String[] args) {//String s= "bab";//String s= "babad";//String s = "ac";String s= "cbbd";//String s= "abdka";//String s= "aacabdkacaa";//String s= "abbcccbbbcaaccbababcbcabca";LongestPalindrome_01_opt2_1 ss = new LongestPalindrome_01_opt2_1();System.out.println(ss.longestPalindrome(s));}
}
这篇关于算法43：动态规划专练（最长回文子串 力扣5题）---范围模型的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
