判断回文字符串

问题

实现一个函数，判断给定字符串是否为回文字符串。回文字符串是指正读和反读都相同的字符串，如 "aba"、"level"。

解答

方法一：双指针

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;
  
  while (left < right) {
    // 左右指针字符不相等，不是回文
    if (str[left] !== str[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

// 测试
console.log(isPalindrome('aba'));    // true
console.log(isPalindrome('abba'));   // true
console.log(isPalindrome('abc'));    // false

方法二：反转比较

function isPalindrome(str) {
  // 反转字符串后与原字符串比较
  const reversed = str.split('').reverse().join('');
  return str === reversed;
}

方法三：递归

function isPalindrome(str) {
  // 空字符串或单字符是回文
  if (str.length <= 1) {
    return true;
  }
  
  // 首尾字符不同，不是回文
  if (str[0] !== str[str.length - 1]) {
    return false;
  }
  
  // 递归检查去掉首尾后的子串
  return isPalindrome(str.slice(1, -1));
}

扩展：忽略大小写和非字母数字字符

function isPalindrome(str) {
  // 转小写，只保留字母和数字
  const cleaned = str.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  let left = 0;
  let right = cleaned.length - 1;
  
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

// 测试
console.log(isPalindrome('A man, a plan, a canal: Panama')); // true
console.log(isPalindrome('race a car'));                      // false

关键点

• 双指针法时间复杂度 O(n)，空间复杂度 O(1)，最优解
• 反转比较法简洁但需要 O(n) 额外空间
• 实际场景常需要预处理：忽略大小写、过滤非字母数字字符
• 递归法直观但有栈溢出风险，不推荐处理长字符串