最长回文子串

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母（大写和/或小写）组成

力扣🔗：https://leetcode-cn.com/problems/longest-palindromic-substring (opens new window)

解题思路

• 依次遍历字符串 s 中的字符直到倒数第一个字符为止，从当前遍历到的字符为起点再次向后遍历每个字符，与每个字符为终点组成子串。
• 通过对称位置字符是否相等判断每条子串是否是回文，如果是且长度大于已存的回文子串，则将其更新为最新的最长回文子串。

PS：😫果真又是令人痛苦面具的一题，动态规划、中心扩散、Manacher 算法，头痛欲裂。工欲善其事必先利其器，看来手里的兵器还得好好磨一磨！👿坚持！

代码实现

/**
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  const l = s.length // 传入字符串的长度

  if (l === 1 || l === 2) {
    return s[1] === undefined ? s[0] : s[0] === s[1] ? s : s[0]
  }

  let result = '' // 保存最长回文子串

  for (let i = 0; i < l - 1; i++) {
    for (let j = i + 1; j <= l; j++) {
      const subStr = s.slice(i, j) // 截取子串

      if (subStr.length > result.length && isPalindrome(subStr)) {
        // 如果截取的字符串长度大于已保存的回文子串长度，且是回文
        result = subStr // 更新最长回文子串
      }
    }
  }

  // 判断传入的字符串是否是回文
  function isPalindrome(subStr) {
    const l = subStr.length

    for (let i = 0; i < parseInt(l / 2); i++) {
      // 判断遍历到的字符与其对称的位置字符是否相同
      if (subStr[i] !== subStr[l - i - 1]) {
        return false
      }
    }
    return true
  }

  return result
}