0005 最长回文子串 - Hero · 算法 · Leetcode

题目地址(0005. 最长回文子串)

https://leetcode.cn/problems/longest-palindromic-substring

题目描述

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。



示例 1：

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

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


提示：

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

JS实现(暴力双循环)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let idx = [0, 1];
  for (let i = 0; i < s.length; i++) {
    for (let j = i + 1; j <= s.length; j++) {
      if (j - i > idx[1] - idx[0] && validPalindromic(s.slice(i, j))) {
        idx[0] = i;
        idx[1] = j;
      }
    }
  }
  return s.slice(idx[0], idx[1]);
};

function validPalindromic(str) {
  let i = 0;
  while (i < str.length / 2) {
    if (str[i] !== str[str.length - i - 1]) return false;
    i++;
  }
  return true;
}

JS实现(暴力双循环 回文串确认优化版)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let targetArr = [0, 1];
  for (let i = 0; i < s.length - 1; i++) {
    for (let j = i + 1; j < s.length; j++) {
      if (targetArr[1] - targetArr[0] < j - i + 1 && isPalindrome(s, i, j)) {
        targetArr = [i, j + 1];
      }
    }
  }
  return s.slice(targetArr[0], targetArr[1]);
};

function isPalindrome(str, left, right) {
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

JS实现(动态规划)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const smap = [];
  let [start, end] = [0, 0];

  for (let j = 0; j < s.length; j++) {
    for (let i = j; i >= 0; i--) {
      if (!smap[i]) smap[i] = [];
      // 单个情况
      if (i === j) {
        smap[i][j] = true;
      } else if (s[i] !== s[j]) {
        smap[i][j] = false;
      } else if (j - i === 1 && s[i] === s[j]) {
        smap[i][j] = true;
        if (end - start < j - i) {
          start = i;
          end = j;
        }
      } else if (s[i] === s[j] && smap[i + 1][j - 1]) {
        smap[i][j] = true;
        if (end - start < j - i) {
          start = i;
          end = j;
        }
      }
    }
  }

  return s.slice(start, end + 1);
};

JS实现(中心扩散)

中心扩散的核心还是在回文串的判断方式上，是从中心扩散的方式j

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) return s.length;
  let maxLen = 1,
    max;
  for (let i = 0; i < s.length - 1; i++) {
    let [s1, e1] = isPalindrome(s, i, i);
    let [s2, e2] = isPalindrome(s, i, i + 1);
    maxLen = Math.max(maxLen, e1 - s1, e2 - s2);
  }
  // TODO: 待补充
  // return s.substring()
};

function isPalindrome(str, left, right) {
  while (left >= 0 && right < str.length) {
    if (str[left] !== str[right]) return [left - 1, right - 1];
    left--;
    right++;
  }
  return [left, right];
}