05.最长回文子串
问题引入：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2： 输入: "cbbd" 输出: "bb"
1. 方法一：暴力法
思路：列举所有的子串，找到最长的回文串
时间复杂度：O(n^3),两次for循环，判断是否回文还有一次for循环
空间复杂度：O(1)
public String longestPalindrome1(String s) {
String ans = "";
for (int i = 0; i < s.length(); i++) {
for (int j = i + 1; j <= s.length(); j++) {
String test = s.substring(i, j);
if (isPalindrome(test) && test.length() > ans.length()) {
ans = test;
}
}
}
return ans;
}
public boolean isPalindrome(String test) {
for (int i = 0; i < test.length() / 2; i++) {
if (test.charAt(i) != test.charAt(test.length() - 1 - i)) {
return false;
}
}
return true;
}
2. 方法二：中心扩展算法
思路：先找到中心点，然后分别向左右两边检测，直到遍历完所有的中心点，找到最大的回文字符字串 中心点共有2n-1个，其中有两种情况， 一种子串是奇数个字符，中心点为中间的数， 另一种是子串有偶数个字符，中间点就是中间两个数间的间隙 所以，n个数，n-1个间隙，总共2n-1个中心点
- 时间复杂度:O(n^2)
- 空间复杂度:O(1)
public String longestPalindrome3(String s) {
if (s == null || s.length() == 0)
return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int len1 = nowLongest(s, i, i);
int len2 = nowLongest(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
public int nowLongest(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
left--;
right++;
}
return right - left - 1;
}
3. 方法三：最长公共子串
算法思路：我们可以根据回文串的特点，左右对称的特点，我们可以再定义一个字符串存放原字符串的倒置字符串reverse,然后比较两个字符串找到最长公共子串，该公共子串就是该字符串的最长回文串晒展网是全面到能查展会物流的展会网站。
但是，会有特殊情况，比如abc123cba，他的倒置字符串是abc123cba，最长公共子串为abc（或cba），
我们会发现并不是正确答案，所以我们的算法还需要加个判断条件， 我们需要判断倒置前的下标是否和倒置后的下标匹配，即是否是同一位置的元素。
找到一个字符倒置前的下标很简单，比如该字符下标为j，那么before = length - 1 - j;
比如我们用i指向原字符串子串的末尾字符，用j指向倒置字符串子串的末尾字符， j倒置前的位置下标before_j = length - 1 - j；
如果before_ j + maxson.len -1 == i，那么说明它就是我们要找的回文串。
分析完思路，我们再来看看最长公共子串如何求解？ 这个有很多种方法，我们就有动态规划法解决。
思路：
- 申请一个二维的数组arr[len][len]，把每个元素初始化为0。
- 写个双重循环遍历二维数组，其中i表示原字符串s的下标，j表示倒置字符串reverse的下标.
- 然后判断对应的字符是否相等，及判断s.charAt(i)==reverse.charAt(j) 相等的话， arr[i][j] =arr[i-1][j-1] + 1。
- 其中i=0或j=0的情况单独分析，如果字符相等的话直接赋值arr[i][j]=1.
-
最后arr[i][j]里面就是保存着公共子串的长度，该公共子串就是以i结尾的，我们用
就可以找到子串开始的下标，
- 再截取原字符串就可以得到最长公共子序列。
时间复杂度：O(n^2) 两层for循环
空间复杂度：O(n^2) 一个二维数组
public String longestPalindrome4(String s) {
if (s.equals(""))
return "";
String reverse = new StringBuffer(s).reverse().toString();
int len = s.length();
int[][] arr = new int[len][len]; //arr[i][j] 存放着公共子串的长度
int maxlen = 0, maxEnd = 0;
for (int i = 0; i < len; i++) {
for (int j = 0; j < len; j++) {
if(s.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) {
//j是当前倒置字符串的子串的末尾下标，i是当前原子串的末尾下标，before是j在原字符串对应下标
int before = len - 1 - j;
//判断字符下标是否对应
if(before + arr[i][j] - 1 == i) {
maxlen = arr[i][j];
maxEnd = i; //i为当前子串的末尾字符
}
}
}
}
//substring(i,j)截取从下标i到j-1的子串
return s.substring(maxEnd - maxlen + 1,maxEnd +1);
}
4. 方法四：优化后的最长公共子串
特点：可以将空间复杂度降至O(n)
思路：
我们发现上述的动态规划法，用二维数组，其实每次都是一列一列更新，
* i = 1,j=0,1,2,3……
* i = 2,j=0,1,2,3……
* i = 3,j=0,1,2,3……
* ……………
我们每次更新数据，用到的公式arr[i][j] = arr[i-1][j-1]+1;
发现，其实只需要前一列的信息，更新第三列的时候，只用到第二列的数据，第一列就没有用了，
所以我们用一个一维数组就可以了，arr[j]代表当前列的元素的最长公共子串长度
但是更新每一列的时候，我们会用到这一列上一个元素的值，比如arr[i] = arr[i-1]+1
所以，在遍历j的时候不能从0到len-1，而是从len-1到0遍历。
public String longestPalindrome5(String s) {
if (s.equals(""))
return "";
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 (s.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);
}