5.最长回文子串

链接：5.最长回文子串
难度：Medium
标签：双指针、字符串、动态规划
简介：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

题解 1 - javascript

• 编辑时间：2020-04-07
• 执行用时：84ms
• 内存消耗：42.6MB
• 编程语言：javascript
• 解法介绍：对每个字符依次判断两边是否相等，相等则+1，不相等则跳过。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  const len = s.length;
  let maxRes = '';
  if (len === 0) return maxRes;
  for (let i = 0; i < len; i++) {
    const c = s[i];
    let left = i - 1;
    let right = i + 1;
    let maxS = c;
    while (i < len && c === s[i + 1]) {
      maxS += c;
      right++;
      i++;
    }
    while (left >= 0 && right <= len - 1) {
      if (s[left] !== s[right]) break;
      maxS = s[left] + maxS + s[right];
      left--;
      right++;
    }
    maxRes = maxS.length > maxRes.length ? maxS : maxRes;
  }
  return maxRes;
};

题解 2 - typescript

• 编辑时间：2021-10-16
• 执行用时：88ms
• 内存消耗：45MB
• 编程语言：typescript
• 解法介绍：马拉车算法。

function longestPalindrome(s: string): string {
  s = createStr(s);
  let max = -1;
  let maxIdx = -1;
  const n = s.length;
  const arr = new Array(n).fill(0);
  let ans = s[0];
  for (let i = 0; i < n; i++) {
    if (i <= max) {
      arr[i] = Math.min(arr[2 * maxIdx - i], max - i);
    }
    let l = i - arr[i];
    let r = i + arr[i];
    while (l - 1 >= 0 && r + 1 <= n - 1 && s[l - 1] === s[r + 1]) {
      l--;
      r++;
    }
    if (r > max) {
      max = r;
      maxIdx = i;
    }
    arr[i] = r - i;
    if (ans.length < r - l + 1) {
      ans = s.substring(l, r + 1);
    }
  }
  return ans.replace(/#/g, '');
  function createStr(s: string) {
    let ans = '#';
    for (let i = 0; s[i]; i++) ans += s[i] + '#';
    return ans;
  }
}