回文判断

如何用对撞指针判断回文串？

• 预处理: 统一转为小写, 去掉非字母数字字符;
• 左右指针分别指向两端并向中间移动;
• 对应字符不同立即返回 false;
• 两指针相遇说明整串是回文;

function isPalindrome(s: string): boolean {
  const t = s.toLowerCase().replace(/[^0-9a-z]/g, "");
  let left = 0;
  let right = t.length - 1;
  while (left < right) {
    if (t[left] !== t[right]) return false;
    left++;
    right--;
  }
  return true;
}

• 时间复杂度: O(s.length), 预处理与遍历各一次;
• 空间复杂度: O(s.length), 预处理产生的新字符串;

字符串反转与回文判断有什么关系？

• 反转字符串同样是对撞指针: 交换左右两端并同时向中间收紧;
• 回文判断只是反转的"判定版", 不要求真的改写数组;
• 回文子串类问题需要中心扩展或动态规划, 不属于本节范围;