LeetCode 5. 最长回文子串 - TypeScript 实现
方法一：中心扩展法（推荐）
时间复杂度: O(n²) |空间复杂度: O(1)
【typescript】
 function longestPalindrome(s: string): string {
  if (s.length < 2) return s;
  let start = 0;
  let maxLen = 1;
  // 中心扩展函数
  const expandAroundCenter = (left: number, right: number): void => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const currentLen = right - left + 1;
      if (currentLen > maxLen) {
        maxLen = currentLen;
        start = left;
      }
      left--;
      right++;
    }
  };
  for (let i = 0; i < s.length; i++) {
    // 奇数长度回文（单字符中心）
    expandAroundCenter(i, i);
    // 偶数长度回文（双字符中心）
    expandAroundCenter(i, i + 1);
  }
  return s.substring(start, start + maxLen);
}
方法二：动态规划
时间复杂度: O(n²) |空间复杂度: O(n²)
【typescript】
 function longestPalindrome(s: string): string {
  const n = s.length;
  if (n < 2) return s;
  // dp[i][j] 表示 s[i..j] 是否为回文
  const dp: boolean[][] = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0;
  let maxLen = 1;
  // 单个字符都是回文
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  // 枚举子串长度
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;
      if (s[i] === s[j]) {
        if (len === 2) {
          dp[i][j] = true;
        } else {
          dp[i][j] = dp[i + 1][j - 1];
        }
      }
      if (dp[i][j] && len > maxLen) {
        maxLen = len;
        start = i;
      }
    }
  }
  return s.substring(start, start + maxLen);
}
方法三：Manacher 算法（最优）
时间复杂度: O(n) |空间复杂度: O(n)
【typescript】
 function longestPalindrome(s: string): string {
  if (s.length < 2) return s;
  // 预处理：插入特殊字符，统一奇偶情况
  // 例: "aba" -> "^#a#b#a#$"
  const t = '^#' + s.split('').join('#') + '#$';
  const n = t.length;
  const p: number[] = new Array(n).fill(0); // p[i] 表示以 t[i] 为中心的回文半径
  let center = 0;  // 当前回文中心
  let right = 0;   // 当前回文右边界
  for (let i = 1; i < n - 1; i++) {
    const mirror = 2 * center - i; // i 关于 center 的对称点
    if (i < right) {
      p[i] = Math.min(right - i, p[mirror]);
    }
    // 尝试扩展
    while (t[i + p[i] + 1] === t[i - p[i] - 1]) {
      p[i]++;
    }
    // 更新中心和右边界
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
  }
  // 找到最大半径及其位置
  let maxLen = 0;
  let centerIndex = 0;
  for (let i = 1; i < n - 1; i++) {
    if (p[i] > maxLen) {
      maxLen = p[i];
      centerIndex = i;
    }
  }
  const start = Math.floor((centerIndex - maxLen) / 2);
  return s.substring(start, start + maxLen);
}
测试用例
【typescript】
 // 测试
console.log(longestPalindrome("babad")); // "bab" 或 "aba"
console.log(longestPalindrome("cbbd"));  // "bb"
console.log(longestPalindrome("a"));     // "a"
console.log(longestPalindrome("ac"));    // "a" 或 "c"
console.log(longestPalindrome("racecar")); // "racecar"
算法对比
【表格】
 方法    时间复杂度    空间复杂度    适用场景    
中心扩展    O(n²)    O(1)    ✅ 面试推荐，简洁高效    
动态规划    O(n²)    O(n²)    需要子问题信息时    
Manacher    O(n)    O(n)    追求极致性能
💡面试建议：优先掌握中心扩展法，思路清晰、代码简洁；如有余力再提 Manacher 算法作为优化方案。