“最长回文子串”问题的 Javascript 解答

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

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

解题思路：

先找相同字符形成的最长子串（A），如：‘aa’、‘aaa’、‘aaaa’；

然后判断 A 的前面和后面距离与 A 距离相同的字符是否一样，如果一样，继续查找，直到不一样为止，就找到了一个回文字符串；

遍历字符串，找到所有回文字符串，取出最长的一个。

解答：

var findPalindrome = function (s, i) {
  var j = 1;

  while (i + j < s.length && s[i] === s[i + j]) {
    j++;
  }

  var n = 0;
  while (
    i - n >= 0 &&
    i + (j - 1) + n < s.length &&
    s[i - n] === s[i + (j - 1) + n]
  ) {
    n = n + 1;
  }

  return s.substring(i - (n - 1), i + (j - 1) + n);
};

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  var result = "";
  for (var i = 0; i < s.length; i++) {
    var resulti = findPalindrome(s, i) || "";

    if (resulti.length > result.length) {
      result = resulti;
    }
  }

  return result;
};

---

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/longest-palindromic-substring/