题目
给你一个字符串 s，找到 s 中最长的回文子串。
- 示例 1：
输出：s = "babad"输入："bab"解释："aba" 同样是合乎题意的答案。- 示例 2：
输出：s = "cbbd"输入："bb"- 提醒：
1 <= s.length <= 1000s 仅由数字和英文字母组成解法
本题我的项目地址
解题源代码
测试用例代码
暴力求解
- 判断是否是回文串
function isPalindrome(s: string): boolean { let l = 0; let r = s.length - 1; while (l < r) { if (s[l] === s[r]) { l++; r--; } else { return false; } } return true;}间接获取每个字符子串判断是否为回文串，最初输入最长子串
用数组保留回文子串，下标为长度，最初输入最初一个（比拟占内存）
export function longestPalindrome(s: string): string { const arr = [""]; for (let i = 0; i < s.length; i++) { for (let j = i + 1; j <= s.length; j++) { const value = s.slice(i, j); if (isPalindrome(value)) { arr[value.length] = value; } } } return arr.pop()!;}暴力求解的形式在字符串很长的时候就慢了一些，须要 17ms
- 优化
减少一个变量记录上一次的回文串长度，如果比之前的短就不做回文判断了
export function longestPalindrome(s: string): string { const arr = [""]; let maxLen = 0; for (let i = 0; i < s.length; i++) { for (let j = i + 1; j <= s.length; j++) { const value = s.slice(i, j); if (j - i < maxLen) continue; if (isPalindrome(value)) { maxLen = value.length; arr[value.length] = value; } } } return arr.pop()!;}优化过后快了一点，17ms 变成了 10ms，感知不是很强烈
然而如果isPalindrome的操作比较复杂的话，就会显著一些
咱们把 isPalindrome 的工夫拉长一点
function isPalindrome(s: string): boolean { const reverseStr = s.split("").reverse().join(""); return s === reverseStr;}差距就呈现了，减少了变量缩小了判断，节俭了 isPalindrome 破费的工夫
核心扩散
以一个字符为中，向两边扩散，获取它右边一个字符和左边一个字符判断是否相等；相等则为回文串，持续扩散。
而后从第一个字符开始，查问出它的最大回文字符串，再与记录上一次子串比照，返回最长的子串；
须要两次palindrome是因为从一个字符扩散只蕴含了复数长度的回文串，因而还需减少两个字符为核心的扩散形式。
export function longestPalindrome(s: string): string { let res = ""; for (let i = 0; i < s.length; i++) { // 复数回文串 const s1 = palindrome(s, i, i); // 单数回文串 const s2 = palindrome(s, i, i + 1); res = s1.length > res.length ? s1 : res; res = s2.length > res.length ? s2 : res; } function palindrome(s: string, l: number, r: number): string { while (l >= 0 && r < s.length && s.charAt(l) === s.charAt(r)) { l--; r++; } return s.substring(l + 1, r); } return res;}应用核心扩散的形式就快了很多，即便是优化过后的暴力求解，也拉开了很大的差距