最长回文子串

题目描述：

给你一个字符串 s，找到 s 中最长的回文子串。

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

输入：s = "cbbd"
输出："bb"

示例3：

输入：s = "a"
输出："a"

链接：

5. 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)

解题思路 

思路一：中心扩展算法

从中心开始不断地向两边扩展。如果两边的字母相同，我们就可以继续扩展

枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。我们对所有的长度求出最大值，即可得到最终的答案

/*** @param {string} s* @return {string}*/
var longestPalindrome = function (s) {if (s.length < 2) {return s;}let start = 0,maxLength = 1; // 对于ab这种情况function expandAroundCenter(left, right) {while (left >= 0 && right < s.length && s[left] == s[right]) {if (maxLength < right - left + 1) {maxLength = right - left + 1;start = left;}left--;right++;}}for (var i = 0; i < s.length; i++) {expandAroundCenter(i - 1, i + 1);  // 针对cacac这种情况expandAroundCenter(i, i + 1);  // 针对babbab}return s.substring(start, start + maxLength);
};

时间复杂度： O(n2)，其中 n 是字符串的长度。

空间复杂度： O(1)

思路二：动态规划

中心扩散的方法，其实做了很多重复计算。动态规划就是为了减少重复计算的问题（空间换时间，将计算结果暂存起来，避免重复计算）。

我们用一个 布尔型二维数组 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

var longestPalindrome = function (s) {let len = s.length,start = 0,maxLength = 1;if (len < 2) {return s;}let dp = Array(len);for (let i = 0; i < len; i++) {dp[i] = [];}for (let r = 1; r < len; r++) {for (let l = 0; l < r; l++) {if (s[l] == s[r] && (r - l <= 2 || dp[l + 1][r - 1])) {dp[l][r] = true;if (r - l + 1 > maxLength) {maxLength = r - l + 1;start = l;}}}}return s.substring(start, start + maxLength);
}; 

时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。

空间复杂度：O(n^2)，即存储动态规划状态需要的空间