5. 最长回文子串 (opens new window)

Description

Difficulty: 中等

Related Topics: 字符串 (opens new window), 动态规划 (opens new window)

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

Solution

Language: JavaScript

/**
 * @param {string} s
 * @return {string}
 * 1 <= s.length <= 1000
 * 
 * start = begin = 0 ; maxLen = 1
 * 
 * 1.中心扩展算法
 */
var longestPalindrome = function(s) {
 const n = s.length;
 let [start, maxLen] = [0, 1]
 const expendAroundMiddle = function(left, right) {
  while (left >= 0 && right < n && s[left] === s[right]) {
   const currLen = right - left + 1
   if (currLen > maxLen) {
    maxLen = currLen
    start = left
   }

   right++
   left--
  }
 }

 for (let i = 0; i < n; i++) {
  expendAroundMiddle(i, i)
  expendAroundMiddle(i, i+1)
 }
 return s.slice(start, start + maxLen)
};