“最长回文子串”问题的 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/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注