力扣-125. 验证回文串

1. 题目

题目地址(125. 验证回文串 - 力扣（LeetCode）)

https://leetcode.cn/problems/valid-palindrome/

题目描述

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

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

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

 

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

示例 2：

输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。

示例 3：

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。

 

提示：

• 1 <= s.length <= 2 * 105
• s 仅由可打印的 ASCII 字符组成

2.题解

2.1 首尾双指针(回文)

思路

首先全部小写, 去除非字母字符, 在处理的时候我是直接对于题目给的string进行处理的, 使用了快慢指针的思想, 由于读到的字符总是快于我当前修改的位置,所以直接原地修改即可
然后使用首尾双指针遍历字符串即可!

代码

• 语言支持：C++

C++ Code:

class Solution {
public:void removeExceptAlpha(string& s) {int i = 0, j = 0;while (j < s.size()) {if (isalnum(s[j])) {s[i++] = tolower(s[j]);}j++;}s.resize(i);}bool isPalindrome(string s) {removeExceptAlpha(s);int i = 0, j = s.length() - 1;while (i < j) {if (s[i++] != s[j--]) return false;}return true;}
};

复杂度分析

由于字符串是不可变的, 这里其实空间复杂度没有改变
令 n 为数组长度。

• 时间复杂度：\(O(n)\)
• 空间复杂度：\(O(n)\)

2.2 首尾双指针(优化空间复杂度为O(1))

思路

遇到不是字母数字字符, 就向后遍历跳过, 注意这里要防止越界, 判断l < r即可

代码

class Solution {
public:bool isPalindrome(string s) {int l = 0, r = s.length() - 1;while (l < r) {while(l < r && !isalnum(s[l])) l++;while(l < r && !isalnum(s[r])) r--;if(l < r){if(tolower(s[l]) != tolower(s[r])) return false;l++; r--;}}return true;}
};