最长回文子串

题目描述

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

示例

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

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

我的解题过程

首先想的就是双指针 然后反转字符串 判断是否是回文字符串

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;

  let max = 0;
  let res = s[0];
  for (let i = 0; i < s.length - 1; i++) {
    for (let j = s.length - 1; j > 0; j--) {
      const str = s.substring(i, j + 1);

      if (str === str.split("").reverse().join("") && str.length > max) {
        max = str.length;
        res = str;
      }
    }
  }
  return res;
}

这样写完运行没问题 但是提交后发现 超时了

所以看了下解题思路 常见的是中心扩展法 和动态规划法

中心扩展法

把每一个字符串的位置作为中心点 向两边扩展 判断是否是回文字符串

错误示例代码：

function longestPalindrome(s: string): string {
  let cur = 0;
  let res = "";

  for (let i = 0; i < s.length - 1; i++) {
    let preIndex = i - 1;
    let nextIndex = i + 1;

    while (preIndex >= 0 && nextIndex < s.length && s[preIndex] === s[nextIndex]) {
      res = s.substring(preIndex, nextIndex + 1);
      preIndex--;
      nextIndex++;
    }
  }

  return res;
}

运行后第一个测试用例是对的 但是第二个就错了 因为可能存在当前的中心点是两个字符（偶数）的情况

所以又出现了一个错误的代码：

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;

  let cur = 0;
  let res = "";

  for (let i = 0; i < s.length - 1; i++) {
    let preIndex = i - 1;
    let nextIndex = i + 1;

    while (
      (preIndex >= 0 && nextIndex < s.length && s[preIndex] === s[nextIndex]) ||
      (preIndex >= 0 && nextIndex < s.length && s[i] === s[nextIndex])
    ) {
      const isOdd = preIndex >= 0 && nextIndex < s.length && s[preIndex] === s[nextIndex];
      const isEven = preIndex >= 0 && nextIndex < s.length && s[i] === s[nextIndex];
      res = s.substring(isOdd ? preIndex : i, nextIndex + 1);
      preIndex--;
      nextIndex++;
    }
  }

  return res;
}

这个代码把奇数和偶数放到一起处理了 但是两个的处理其实是不同的 所以还是错的

最终正确代码如下：

function longestPalindrome(s: string): string {
  if (s.length < 2) return s;

  let res = s[0];

  for (let i = 0; i < s.length; i++) {
    // ---------- 奇数回文 ----------
    let preIndex = i - 1;
    let nextIndex = i + 1;

    while (preIndex >= 0 && nextIndex < s.length && s[preIndex] === s[nextIndex]) {
      const cur = s.substring(preIndex, nextIndex + 1);
      if (cur.length > res.length) {
        res = cur;
      }
      preIndex--;
      nextIndex++;
    }

    // ---------- 偶数回文 ----------
    let evenPreIndex = i;
    let evenNextIndex = i + 1;

    while (evenPreIndex >= 0 && evenNextIndex < s.length && s[evenPreIndex] === s[evenNextIndex]) {
      const cur = s.substring(evenPreIndex, evenNextIndex + 1);
      if (cur.length > res.length) {
        res = cur;
      }
      evenPreIndex--;
      evenNextIndex++;
    }
  }

  return res;
}

运行通过 所有测试用例都正确 也没有超时 优化后代码

function longestPalindrome(s: string): string {
    if (s.length < 2) return s;

    let res = s[0];

    const expandAroundCenter = (left: number, right: number) => {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
        const cur = s.substring(left, right + 1);
        if (cur.length > res.length) {
            res = cur;
        }
        left--;
        right++;
        }
    };

    for (let i = 0; i < s.length; i++) {
        // 奇数回文
        expandAroundCenter(i, i);
        // 偶数回文
        expandAroundCenter(i, i + 1);
    }

    return res;
    }
    ```