暑期算法 第二题

题目

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

输入:s = "babad"
输出:"bab"
解释:"aba" 同样是符合题意的答案。
输入:s = "cbbd"
输出:"bb"
输入:s = "a"
输出:"a"
输入:s = "ac"
输出:"a"

来源:LeetCodeHOT100-5

题解

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) {
    return s;
  }
  var res = "";
  for (let i = 0; i < s.length; i++) {
    diff(i, i);//奇数回文扩散
    diff(i, i + 1);//偶数回文扩散
  }

  function diff(m, n) {
    while (m >= 0 && n < s.length && s[m] == s[n]) {
      m--;
      n++;
    }
    if (n - m - 1 > res.length) {//保留最长回文子串
      res = s.slice(m + 1, n);
    }
  }
  return res;
};

题析

中心扩散法:利用回文子串中心对称的特点,每一个字符都视作为中心,往两边扩散。

偶数子串和奇数子串两种情况都需要考虑。

题外

这题暴力也能做,但时间复杂度会到O(n3)O(n^3)