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 = acdbbdaa 我们需要寻找从第一个 b（位置为 3）出发最长回文串为多少。怎么寻找？ 首先往左寻找与当期位置相同的字符，直到遇到不相等为止。 然后往右寻找与当期位置相同的字符，直到遇到不相等为止。 最后左右双向扩散，直到左和右不相等。如下图所示：
每个位置向两边扩散都会出现一个窗口大小（len）。如果 len>maxLen(用来表示最长回文串的长度）。则更新 maxLen 的值。 因为我们最后要返回的是具体子串，而不是长度，因此，还需要记录一下 maxLen 时的起始位置（maxStart），即此时还要 maxStart=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 做缓存有异曲同工之妙。 我们用一个 boolean 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);}Medium