力扣算法动态规划#5最长回文字串

本是古典何须时尚 2023-10-11 11:54 38阅读 0赞

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”  
输出: “bab”  
注意: “aba” 也是一个有效答案。  
示例 2：

输入: “cbbd”  
输出: “bb”

对于这个题，我的理解是暴力算法，但是暴力算法出来的测试用力不通过  
以下是暴力求解的做法  
解法 1: 暴力破解

暴力求解，列举所有的子串，判断是否为回文串，保存最长的回文串。

java  
public boolean isPalindromic(String s) \{  
int len = s.length();  
for (int i = 0; i < len / 2; i++) \{  
if (s.charAt(i) != s.charAt(len - i - 1)) \{  
return false;  
\}  
\}  
return true;  
\}

// 暴力解法  
public String longestPalindrome(String s) \{  
String ans = “”;  
int max = 0;  
int len = s.length();  
for (int i = 0; i < len; i++)  
for (int j = i + 1; j <= len; j++) \{  
String test = s.substring(i, j);  
if (isPalindromic(test) && test.length() > max) \{  
ans = s.substring(i, j);  
max = Math.max(max, ans.length());  
\}  
\}  
return ans;  
\}  
时间复杂度：两层 for 循环 O(n²）O(n²），for 循环里边判断是否为回文 O(n）O(n），所以时间复杂度为 O(n³）O(n³）。

空间复杂度：O(1）O(1），常数个变量。

解法 2: 最长公共子串

根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了。例如 S = “caba” ，S = “abac”，最长公共子串是 “aba”，所以原字符串的最长回文串就是 “aba”。

关于求最长公共子串（不是公共子序列），有很多方法，这里用动态规划的方法，  
整体思想就是，申请一个二维的数组初始化为 0，然后判断对应的字符是否相等，相等的话

arr \[ i \]\[ j \] = arr \[ i - 1 \]\[ j - 1\] + 1 。

当 i = 0 或者 j = 0 的时候单独分析，字符相等的话 arr \[ i \]\[ j \] 就赋为 1 。

arr \[ i \]\[ j \] 保存的就是公共子串的长度。

java  
public String longestPalindrome(String s) \{  
if (s.equals(""))  
return “”;  
String origin = s;  
String reverse = new StringBuffer(s).reverse().toString(); //字符串倒置  
int length = s.length();  
int\[\]\[\] arr = new int\[length\]\[length\];  
int maxLen = 0;  
int maxEnd = 0;  
for (int i = 0; i < length; i++)  
for (int j = 0; j < length; j++) \{  
if (origin.charAt(i) == reverse.charAt(j)) \{  
if (i == 0 || j == 0) \{  
arr\[i\]\[j\] = 1;  
\} else \{  
arr\[i\]\[j\] = arr\[i - 1\]\[j - 1\] + 1;  
\}  
\}  
if (arr\[i\]\[j\] > maxLen) \{  
maxLen = arr\[i\]\[j\];  
maxEnd = i; //以 i 位置结尾的字符  
\}

}
    }
    return s.substring(maxEnd - maxLen + 1, maxEnd + 1);

再看一个例子，S=“abc435cba”，S=“abc534cba”，最长公共子串是 “abc” 和 “cba”，但很明显这两个字符串都不是回文串。

所以我们求出最长公共子串后，并不一定是回文串，我们还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。

比如 S=“caba”，S’=“abac” ，S’ 中 aba 的下标是 0 1 2 ，倒置前是 3 2 1，和 S 中 aba 的下标符合，所以 aba 就是我们需要找的。当然我们不需要每个字符都判断，我们只需要判断末尾字符就可以。

首先 i，j 始终指向子串的末尾字符。所以 j 指向的红色的 a 倒置前的下标是 beforeRev = length-1-j=4-1-2=1，对应的是字符串首位的下标，我们还需要加上字符串的长度才是末尾字符的下标，也就是 beforeRev+arr\[i\]\[j\]-1=1+3-1=3，因为 arr\[i\]\[j\] 保存的就是当前子串的长度，也就是图中的数字 3。此时再和它与 i 比较，如果相等，则说明它是我们要找的回文串。

之前的 S=“abc435cba”，S’=“abc534cba”，可以看一下图示，为什么不符合。

当前 j 指向的 c，倒置前的下标是 beforeRev=length-1-j=9-1-2=6，对应的末尾下标是beforeRev+arr\[i\]\[j\]-1=6+3-1=8，而此时 i=2，所以当前的子串不是回文串。

代码的话，在上边的基础上，保存 maxLen 前判断一下下标匹不匹配就可以了。

Java  
public String longestPalindrome(String s) \{  
if (s.equals(""))  
return “”;  
String origin = s;  
String reverse = new StringBuffer(s).reverse().toString();  
int length = s.length();  
int\[\]\[\] arr = new int\[length\]\[length\];  
int maxLen = 0;  
int maxEnd = 0;  
for (int i = 0; i < length; i++)  
for (int j = 0; j < length; j++) \{  
if (origin.charAt(i) == reverse.charAt(j)) \{  
if (i == 0 || j == 0) \{  
arr\[i\]\[j\] = 1;  
\} else \{  
arr\[i\]\[j\] = arr\[i - 1\]\[j - 1\] + 1;  
\}  
\}  
/**修改的地方**\*\*\*\*\*\*\*\*\*/  
if (arr\[i\]\[j\] > maxLen) \{  
int beforeRev = length - 1 - j;  
if (beforeRev + arr\[i\]\[j\] - 1 == i) \{ //判断下标是否对应  
maxLen = arr\[i\]\[j\];  
maxEnd = i;  
\}  
/\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*/  
\}  
\}  
return s.substring(maxEnd - maxLen + 1, maxEnd + 1);  
\}  
时间复杂度：两层循环 O(n²)O(n²)。

空间复杂度：一个二维数组 O(n²)O(n²)。

空间复杂度其实可以再优化一下。

我们分析一下循环，i=0，j=0，1，2…8 更新一列，然后 i=1，再更新一列，而更新的时候我们其实只需要上一列的信息，更新第 3 列的时候，第 1 列的信息是没有用的。所以我们只需要一个一维数组就可以了。但是更新 arr \[i\] 的时候我们需要 arr\[i-1\] 的信息，假设 a\[3\]=a\[2\]\]+1，更新 a\[4\] 的时候， 我们需要 a\[3\] 的信息，但是 a\[3\] 在之前已经被更新了，所以 j 不能从0到 8，应该倒过来，a\[8\]=a\[7\]+1，a\[7\]=a\[6\]+1, 这样更新 a\[8\] 的时候用 a\[7\]，用完后才去更新 a\[7\]，保证了不会出错。

Java  
public String longestPalindrome(String s) \{  
if (s.equals(""))  
return “”;  
String origin = s;  
String reverse = new StringBuffer(s).reverse().toString();  
int length = s.length();  
int\[\] arr = new int\[length\];  
int maxLen = 0;  
int maxEnd = 0;  
for (int i = 0; i < length; i++)  
/**修改的地方**\*\*\*\*\*\*\*\*\*\*\*\*\*/  
for (int j = length - 1; j >= 0; j–) \{  
/***/  
if (origin.charAt(i) == reverse.charAt(j)) \{  
if (i == 0 || j == 0) \{  
arr\[j\] = 1;  
\} else \{  
arr\[j\] = arr\[j - 1\] + 1;  
\}  
/修改的地方/  
//之前二维数组，每次用的是不同的列，所以不用置 0 。  
\} else \{  
arr\[j\] = 0;  
\}  
/***\*\*\*\*\*\*\*\*\*\*\*\*\*/  
if (arr\[j\] > maxLen) \{  
int beforeRev = length - 1 - j;  
if (beforeRev + arr\[j\] - 1 == i) \{  
maxLen = arr\[j\];  
maxEnd = i;  
\}

}
        }
    return s.substring(maxEnd - maxLen + 1, maxEnd + 1);

\}  
时间复杂度 O(n²)O(n²)。

空间复杂度降为 O(n)O(n)。

最后这个测试用例即可通过，但是还不是最优解！！！！