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

回文子串是指一个字符串中的子序列,该子序列正读和反读都是一样的。比如 “level”,“abccba”

解题思路

要找到一个字符串中的最长回文子串,可以采用中心扩展法。这种方法的基本思想是从字符串的每个字符(以及每对相邻字符)出发,向两边扩展,直到不再是回文为止。这样可以找到以每个字符为中心的所有回文子串,并从中选出最长的那个。

解题步骤

  1. 边界情况处理:如果字符串长度小于等于1,直接返回原字符串。
  2. 初始化变量:定义变量 max 来临时存储最长回文子串。
  3. 遍历字符串:对于每个字符,尝试两种情况:
    • 以该字符为中心的回文子串(奇数长度)
    • 以该字符及其右边的字符为中心的回文子串(偶数长度)
  4. 扩展回文子串:使用双指针 left 和 right 向两边扩展,检查是否仍然是回文。
  5. 记录最长回文子串:如果 helper 返回的回文子串比已知的最长回文子串还要长,更新 max
  6. 返回结果:遍历结束后返回 max

typescript代码实现

/**
 * @param {string} s
 * @return {string}
 */
const longestPalindrome = (s: string) => {
  if (s.length < 2) return s; // 边界条件

  let max: string = ""; // 存储最长回文子串
  for (let i = 0; i < s.length; i++) {
    helper(i, i); // 考虑奇数长度
    helper(i, i + 1); // 考虑偶数长度
  }

  // 辅助函数,寻找回文子串
  function helper(l: number, r: number) {
    while (l >= 0 && r <= s.length - 1 && s[l] === s[r]) {
      l--; // 向左扩展
      r++; // 向右扩展
    }
    const maxStr = s.slice(l + 1, r + 1 - 1);
    if (maxStr.length > max.length) max = maxStr;
  }

  return max;
};

此算法的时间复杂度为 O(n^2) 其中 n 是字符串的长度,因为需要对每个字符尝试构建回文子串并进行比较。空间复杂度为 O(1)

本文为原创,未经授权,禁止任何媒体或个人自媒体转载
商业侵权必究,如需授权请联系340443366@qq.com
标签: 算法