125. 验证回文串

🟢   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string s, return true if it is a palindrome , or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama"

Output: true

Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car"

Output: false

Explanation: "raceacar" is not a palindrome.

Example 3:

Input: s = " "

Output: true

Explanation: s is an empty string "" after removing non-alphanumeric characters.

Since an empty string reads the same forward and backward, it is a palindrome.

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of printable ASCII characters.

题目大意

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true；否则，返回 false。

解题思路

1. 字符串预处理：
   • 首先将字符串 s 转换为小写，忽略大小写敏感性。
2. 双指针法：
   • 定义两个指针 left 和 right，分别指向字符串的头部和尾部。通过这两个指针向中间靠拢，同时进行判断。
3. 跳过非字母和数字字符：
   • 如果 left 指向的字符不是字母或数字，左指针 left 右移一位。
   • 如果 right 指向的字符不是字母或数字，右指针 right 左移一位。
4. 比较字符：
   • 如果当前 left 和 right 指向的字符不相等，则字符串不是回文，返回 false。
   • 如果字符相等，继续移动指针，left 向右移动，right 向左移动。
5. 结束条件：
   • 当 left 大于 right 时，说明所有字符已经被成功比较且相等，字符串是回文，返回 true。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度。
  • 将字符串 s 转换为小写的操作（s.toLowerCase()）需要遍历整个字符串，时间复杂度为 O(n)；
  • 双指针遍历，每个字符最多被访问两次（一次由左指针，一次由右指针），遍历的总时间复杂度为 O(n)；
• 空间复杂度：O(1)，因为只使用了常数空间的指针和变量。

代码

/**
 * @param {string} s
 * @return {boolean}
 */
var isPalindrome = function (s) {
	// 将字符串转换为小写，忽略大小写
	s = s.toLowerCase();
	let left = 0;
	let right = s.length - 1;

	// 使用双指针法
	while (left <= right) {
		// 如果左指针指向的不是字母或数字，则跳过
		if (!isChar(s[left])) {
			left++;
		}
		// 如果右指针指向的不是字母或数字，则跳过
		else if (!isChar(s[right])) {
			right--;
		}
		// 如果左右字符不相等，则不是回文
		else if (s[left] !== s[right]) {
			return false;
		}
		// 如果相等，继续比较下一个字符
		else {
			left++;
			right--;
		}
	}
	return true; // 所有字符比较相等，是回文
};

// 辅助函数：判断是否是字母或数字
var isChar = function (i) {
	return (i >= 'a' && i <= 'z') || (i >= '0' && i <= '9');
};

相关题目

题号	标题	题解	标签	难度
234	回文链表	[✓]	栈 递归 链表 1+
680	验证回文串 II		贪心 双指针 字符串
2002	两个回文子序列长度的最大乘积		位运算 字符串 动态规划 2+
2108	找出数组中的第一个回文字符串		数组 双指针 字符串
2330	验证回文串 IV 🔒		双指针 字符串
3035	回文字符串的最大数量		贪心 数组 哈希表 3+