5.最长回文子串

题目链接：5. 最长回文子串 - 力扣（Leetcode）

看完别人的文章后的思路1：中心扩散法（第一次见，需掌握） 文章5. 最长回文子串 - 力扣（Leetcode）

        首先往左寻找与当期位置相同的字符，直到遇到不相等为止。 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。 最后左右双向扩散，直到左和右不相等。

        每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。 因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=len。

        

看完别人的文章后的思路2：动态规划 文章5. 最长回文子串 - 力扣（Leetcode）

        根据回文串的定义，正着和反着读一样，那我们是不是把原来的字符串倒置了，然后找最长的公共子串就可以了，因此此题就可以变为最长公共子串问题

        动规五步曲，并且题目说了是子串，说明是要连续比较，找到最长公共子串的最大开始索引位置和最大结束索引位置

（1）确定dp数组及其含义

        dp[i][j] 表示在区间 [0,i - 1]上的字符串s和在区间 [0,j - 1] 上的字符串rs的最长公共子串的长度为dp[i][j] 

（2）确定递推公式

        a. 如果s[i] == rs[j]，dp[i][j] = dp[i - 1][j - 1] + 1;

        b. 如果s[i] != rs[j]，dp[i][j] = Math.max(dp[i][j - 1],dp[i - 1][j]);

（3）初始化

        dp[0][j] 应该都为 0

        dp[i][0] 应该都为 0

（4）确定遍历顺序

        从前往后，从上到下

（5）举例推导验证

巩固的知识：

（1）java中如何将char转换为string，利用String.valueOf(char);

（2）String类型的substring方法

（3）如何将字符串颠倒，String rs = new StringBuilder(s).reverse().toString();

实现代码遇到的问题：

（1）写代码的忽视了一个问题，所求的最长公共子串不一定就是回文串

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

        当然我们不需要每个字符都判断，我们只需要判断末尾字符就可以。

（2）中心扩散法中为什么最后的结果里时maxStart加1，原因如下

        细想一下，当left遇到和right字符不想等时，上一个while已经对left进行了--，所以此时回文串的位置应该时left + 1的位置

Java代码：（思路1中心扩散法）

public class Solution{public String longestPalindrome(String s) {if (s == null || s.length() == 0) {return "";}int strLen = s.length();int left = 0;int right = 0;int len = 1;int maxStart = 0;int maxLen = 0;for (int i = 0; i < strLen; i++) {left = i - 1;right = i + 1;//向左扩散，遇到不相同字符时退出循环while (left >= 0 && s.charAt(left) == s.charAt(i)) {len++;left--;}//向右扩散，遇到不相同字符时退出循环while (right < strLen && s.charAt(right) == s.charAt(i)) {len++;right++;}//细想一下，当left遇到和right字符不想等时，上一个while已经对left进行了--，所以此时回文串的位置应该时left + 1的位置while (left >= 0 && right < strLen && s.charAt(right) == s.charAt(left)) {len = len + 2;left--;right++;}if (len > maxLen) {maxLen = len;maxStart = left;}len = 1;}return s.substring(maxStart + 1, maxStart + maxLen + 1);}
}

Java代码：（思路2动态规划）

public class Solution{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);}
}