回文字符串和最长回文子串怎样判断？

简答

回文就是正着读和倒着读一样的字符串，比如 level、abba。最直接的判断是 s === s.split('').reverse().join('')，但它要额外建数组和新字符串。更省的做法是两个指针，一个从头、一个从尾往中间走，每一步比较两个字符，有一处不同就不是回文，O(n) 时间、O(1) 空间。

面试常见的变体是忽略大小写和标点，比如 A man, a plan, a canal: Panama 算回文。做法是指针遇到非字母数字字符就跳过，比较时都转成小写。

最长回文子串要找出字符串里最长的回文片段。思路是中心扩展：回文一定关于中心对称，所以枚举每个可能的中心，向两边扩到不相等为止。中心有两种，奇数长度的回文中心是一个字符，比如 aba 的 b；偶数长度的中心在两个字符之间，比如 abba 的两个 b 中间。长度为 n 的字符串共有 2n-1 个中心，每个最多扩 O(n)，总共 O(n²)。

要注意两点：只枚举单字符中心会漏掉所有偶数长度的回文；按下标比较的是 UTF-16 编码单元，emoji 这类字符会被拆成两半，要按用户看到的字符处理时先用 Array.from 拆分。

判断回文

先看基础版本，再看忽略标点的版本里指针怎样跳过不相干的字符。

JavaScript

function isPalindrome(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

const isAlphanumeric = (char) => /[a-z0-9]/i.test(char);

function isPalindromeLoose(s) {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (!isAlphanumeric(s[left])) {
      left++;
    } else if (!isAlphanumeric(s[right])) {
      right--;
    } else if (s[left].toLowerCase() !== s[right].toLowerCase()) {
      return false;
    } else {
      left++;
      right--;
    }
  }
  return true;
}

console.log(isPalindrome('level')); // true
console.log(isPalindrome('abba')); // true
console.log(isPalindrome('abc')); // false
console.log(isPalindrome('')); // true
console.log(isPalindrome('a')); // true
console.log(isPalindromeLoose('A man, a plan, a canal: Panama')); // true
console.log(isPalindromeLoose('race a car')); // false
console.log(isPalindromeLoose(',.')); // true

循环条件为什么是 left < right 而不是 <=？两个指针相遇时指向同一个字符，自己和自己一定相等，不用比。奇数长度时它们停在正中间，偶数长度时交错而过，两种情况都正好比完所有对称位置。空字符串和单个字符一次都不比较，直接返回 true。

,. 为什么是 true？两个字符都不是字母数字，全部被跳过，剩下的是空串，按约定算回文。这里用的正则 /[a-z0-9]/i 只认 ASCII 字母和数字；题目要支持中文等其他文字时，可以改成带 u 标志的 Unicode 属性类 /[\p{L}\p{N}]/u。

最长回文子串

expand 从给定的左右下标出发往外扩，返回扩到的回文长度。主循环对每个 i 调用两次，分别对应奇数中心和偶数中心。

JavaScript

function longestPalindrome(s) {
  if (s.length < 2) return s;
  let start = 0;
  let maxLength = 1;

  function expand(left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    // 循环停下时两端已经多走了一步，真正的回文是 left+1 到 right-1
    return right - left - 1;
  }

  for (let i = 0; i < s.length; i++) {
    const length = Math.max(expand(i, i), expand(i, i + 1));
    if (length > maxLength) {
      maxLength = length;
      start = i - Math.floor((length - 1) / 2);
    }
  }
  return s.slice(start, start + maxLength);
}

console.log(longestPalindrome('babad')); // bab
console.log(longestPalindrome('cbbd')); // bb
console.log(longestPalindrome('forgeeksskeegfor')); // geeksskeeg
console.log(longestPalindrome('a')); // a
console.log(longestPalindrome('ac')); // a
console.log(longestPalindrome('aaaa')); // aaaa
console.log(JSON.stringify(longestPalindrome(''))); // ""

babad 为什么返回 bab 而不是 aba？两个都是长度 3 的回文。代码只在长度严格变大时更新，bab 以下标 1 为中心，先被找到，后来的 aba 长度相同，不会覆盖。题目一般接受任意一个。

起点 i - Math.floor((length - 1) / 2) 怎么来的？回文的中心在 i（奇数）或 i 与 i + 1 之间（偶数），左半边的长度是 (length - 1) / 2 向下取整。比如 cbbd 里 bb 的中心在下标 1 和 2 之间，length 是 2，起点是 1 - 0 = 1；aaaa 在 i = 1 时偶数中心扩出长度 4，起点是 1 - 1 = 0。

为什么要两种中心？cbbd 的答案 bb 是偶数长度，只用 expand(i, i) 的话，每个中心都只能扩出长度 1，结果会错成 c。

复杂度和更快的做法

中心扩展有 2n-1 个中心，每次扩展最多走 O(n) 步，最坏情况是 aaaa… 这种全相同的字符串，总时间 O(n²)，只用几个变量，空间 O(1)。

另一种常见写法是动态规划：dp[i][j] 表示 s[i..j] 是不是回文，它成立当且仅当两端字符相等且 dp[i+1][j-1] 成立。时间同样 O(n²)，但要 O(n²) 的表格，所以面试里中心扩展更常用。存在 O(n) 的 Manacher 算法，它利用已经找到的回文的对称性跳过重复扩展，实现细节多，一般知道名字和思路就够了。

常见追问

最多删除一个字符后能不能成为回文？

还是两个指针从两头比。遇到第一处不相等时，有两种删法：删左边字符，检查 left + 1 到 right 是不是回文；或者删右边，检查 left 到 right - 1。两种有一种成立就返回 true。整体仍是 O(n)。

为什么 split('').reverse().join('') 处理 emoji 会出错？

split('') 按 UTF-16 编码单元拆分，一个 emoji 通常占两个编码单元，反转后两半的顺序颠倒，得到的就不是原来的字符了。改成 Array.from(s) 或展开 [...s]，会按码点拆分，常见 emoji 就不会被拆开；带肤色或组合的 emoji 由多个码点组成，还需要 Intl.Segmenter 按字素拆分，见《为什么字符串 length 不一定等于用户看到的字符数？》。