给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法一：暴力解法
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²），for 循环里边判断是否为回文，O（n），所以时间复杂度为 O（n³）。
空间复杂度：O（1），常数个变量。
解法二 ：最长公共子串
求两个字符串的最长公共子串 参考：https://blog.csdn.net/u010397369/article/details/38979077
问题：有两个字符串str和str2，求出两个字符串中最长公共子串长度。
比如：str=acbcbcef，str2=abcbced，则str和str2的最长公共子串为bcbce，最长公共子串长度为5。
算法思路：
1、把两个字符串分别以行和列组成一个二维矩阵。
2、比较二维矩阵中每个点对应行列字符中否相等，相等的话值设置为1，否则设置为0。
3、通过查找出值为1的最长对角线就能找到最长公共子串。
针对于上面的两个字符串我们可以得到的二维矩阵如下：
从上图可以看到，str和str2共有5个公共子串，但最长的公共子串长度为5。
为了进一步优化算法的效率，我们可以再计算某个二维矩阵的值的时候顺便计算出来当前最长的公共子串的长度，即某个二维矩阵元素的值由item[i][j]=1演变为item[i][j]=1 +item[i-1][j-1]，这样就避免了后续查找对角线长度的操作了。修改后的二维矩阵如下：
代码实现
/**
* 获取两个字符串最长公共子串长度
* @param str 第一个字符串
* @param str2 第二个字符串
* @return 如果存在则返回最长公共子串长度，否则返回0
*/
public static int getLCSLength(String str, String str2){
char[] ary = str.toCharArray();
char[] ary2 = str2.toCharArray();
int[][] temp = new int[ary.length][ary2.length]; //声明一个二维数组，存储最长公共子串长度
int length = 0; //最长公共子串长度
for (int i = 0; i < ary.length; i++) {
for (int j = 0; j < ary2.length; j++) {
if(ary[i] == ary2[j]){
if(i > 0 && j > 0){
temp[i][j] = temp[i-1][j-1] + 1;
}else{
temp[i][j] = 1;
}
if(temp[i][j] > length){ //当前元素值大于最大公共子串长度
length = temp[i][j];
}
}else{
temp[i][j] = 0;
}
}
}
return length;
}
再看一个例子，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 前判断一下下标匹不匹配就可以了。
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²）。
空间复杂度其实可以再优化一下。
我们分析一下循环，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 ]，保证了不会出错。
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）。
