Medium-最长回文子串
题目
//给你一个字符串 s，找到 s 中最长的回文子串。
//
//
//
// 示例 1：
//
//
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
//
//
// 示例 2：
//
//
//输入：s = "cbbd"
//输出："bb"
//
//
// 示例 3：
//
//
//输入：s = "a"
//输出："a"
//
//
// 示例 4：
//
//
//输入：s = "ac"
//输出："a"
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 1000
// s 仅由数字和英文字母（大写和/或小写）组成
//
// Related Topics 字符串 动态规划
// 3257 0//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public String longestPalindrome(String s) {}
}
//leetcode submit region end(Prohibit modification and deletion)解题思路：
本题最容易想到的一种方法应该就是 中心扩散法。
中心扩散法怎么去找回文串？
从每一个位置出发，向两边扩散即可。遇到不是回文的时候结束。举个例子，str = 我们需要寻找从第一个 b（位置为 3）出发最长回文串为多少。怎么寻找？
然后往右寻找与当期位置相同的字符，直到遇到不相等为止。
最后左右双向扩散，直到左和右不相等。如下图所示：
每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>(用来表示最长回文串的长度）。则更新 的值。
因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 时的起始位置（），即此时还要 =len。
代码：
public String longestPalindrome1(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++;}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);}
优化：
中心扩散的方法，其实做了很多重复计算。动态规划就是为了减少重复计算的问题。动态规划听起来很高大上。其实说白了就是空间换时间，将计算结果暂存起来，避免重复计算。作用和工程中用 redis 做缓存有异曲同工之妙。
我们用一个 dp[l][r] 表示字符串从 i 到 j 这段是否为回文。试想如果 dp[l][r]=true，我们要判断 dp[l-1][r+1] 是否为回文。只需要判断字符串在(l-1)和（r+1)两个位置是否为相同的字符，是不是减少了很多重复计算。
进入正题，动态规划关键是找到初始状态和状态转移方程。
初始状态，l=r 时，此时 dp[l][r]=true。
状态转移方程，dp[l][r]=true 并且(l-1)和（r+1)两个位置为相同的字符，此时 dp[l-1][r+1]=true。
代码：
public String longestPalindrome(String s) {if (s == null || s.length() < 2) {return s;}int strLen = s.length();int maxStart = 0; //最长回文串的起点int maxEnd = 0; //最长回文串的终点int maxLen = 1; //最长回文串的长度boolean[][] dp = new boolean[strLen][strLen];for (int r = 1; r < strLen; r++) {for (int l = 0; l < r; l++) {if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {dp[l][r] = true;if (r - l + 1 > maxLen) {maxLen = r - l + 1;maxStart = l;maxEnd = r;}}}}return s.substring(maxStart, maxEnd + 1);}
