题目
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2：
输入：s = "cbbd" 输出："bb" 示例 3：
输入：s = "a" 输出："a" 示例 4：
输入：s = "ac" 输出："a"
提示：
1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成
思路
要做这道题需要理解什么是回文和子串
- 回文：从左到右和从右到左的顺序是一样的，具有轴对称的特性
- 子串：子串是原始字符串的连续部分
既然具有轴对称的特性，首先想到的就是通过轴的字符串向两边扩展，这样又出现两种情况
- 奇数对称，比如“bab”这种形式，这种需要对比左右两个字符是否相等
- 偶数对称，比如“baab”这种形式，这种需要比较当前和左、右是否相等
代码实现
public static String longestPalindrome(String s) { //不需要保存子串，只需要记住起始位置和长度即可 int maxStart = 0, maxLen = 0; for (int i = 0; i < s.length(); i++) { int left = i - 1; int right = i + 1; int currLen = 1; //偶数对称，当前字符和左侧字符相等, 回文子串长度+1 while (left >= 0 && s.charAt(left) == s.charAt(i)) { currLen++; left--; } //偶数对称，当前字符和右侧字符相等，回文子串长度+1 while (right < s.length() && s.charAt(right) == s.charAt(i)) { currLen++; right++; } //奇数对称， 当前字符的左右两侧字符相等，回文子串长度+2 while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) { currLen = currLen + 2; left--; right++; } if (currLen > maxLen) { maxLen = currLen; maxStart = left; } } return s.substring(maxStart + 1, maxStart + maxLen + 1); }
执行用时：44 ms, 在所有 Java 提交中击败了60.33%的用户
内存消耗：38.1 MB, 在所有 Java 提交中击败了97.80%的用户
优化
上面的解法其实做了很多重复计算，动态规划就是为了减少重复计算的问题。动态规划听起来很高大上。其实说白了就是空间换时间，将计算结果暂存起来，避免重复计算。
回文天然具有状态转移性质：一个回文去掉头尾字符以后，剩下的部分依然是回文。反之，如果一个字符串头尾两个字符都不相等，那么这个字符串一定不是回文。动态规划的方法根据这样的性质得到。
第 1 步：定义状态dp[i][j] 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]。
第 2 步：状态转移方程根据头尾字符是否相等，推导该段字符串是否是回文取决于去掉头尾后是否是回文
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
第3步：初始化
初始化一个boolean二维数组，通过标志位来标识是否是回文
public String longestPalindrome(String s) { if (s == null || s.length() < 2) { return s; } int maxStart = 0; int maxEnd = 0; int maxLen = 1; boolean[][] dp = new boolean[s.length()][s.length()]; for (int r = 1; r < s.length(); r++) { for (int l = 0; l < r; l++) { //r - l <= 2 此处是为了解决l+1和r-1是同一个数时的情况，这种情况也就是初始值为true 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); }
小结
这道题开始涉及常见的动态规划思路了，再遇到几个动态规划题目后，会尝试总结一下动态规划的模板，这样再遇到后就不会一脸懵逼，至少有一点思路。
