LeetCode 面试经典 150_双指针_验证回文串（25_125_C++_简单）(双指针)

题目描述：

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

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

给你一个字符串 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 * 10⁵
s 仅由可打印的 ASCII 字符组成

题解：

解题思路：

思路一（双指针）：

1、首先将大写字母转换为小写字母，保留数字,移除所有的其他字符。再通过双指针来判断是否是回文串，初始时指针在字符串的头和尾。

2、复杂度分析：
① 时间复杂度：O(n)，n 为字符串中字符的个数，挑选出字母和数字，并将大写字母转换为小写 O(n)。遍历一遍挑选出来的字符进行回文判断O(n)。
② 空间复杂度：O(n)，最坏的情况下原字符串只包含字母和数字。
（也可使用原字符串存储挑出来的字符，使用双指针实现。那空间复杂度就为O（1））

代码实现

代码实现（思路一（双指针））：

class Solution {
public:bool isPalindrome(string s) {// 创建一个新的字符串，存放处理后的字符（只保留字母和数字，并转为小写）string s_processed = "";// 遍历输入字符串 sfor (auto &i : s) {// 如果当前字符是字母或数字，则加入到 s_processed 中，并转为小写（数字则不变）if (isalnum(i)) {s_processed += tolower(i);}}// 设置左右指针，分别指向处理后字符串的开始和结束位置int left = 0, right = s_processed.size() - 1;// 使用双指针法进行比较while (left < right) {// 如果左右指针指向的字符不相同，则返回 falseif (s_processed[left] != s_processed[right]) {return false;}// 移动左右指针，继续向中间比较left++;right--;}// 如果所有字符都匹配，返回 truereturn true;}
};

以思路一为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution {
public:bool isPalindrome(string s) {// 创建一个新的字符串，存放处理后的字符（只保留字母和数字，并转为小写）string s_processed = "";// 遍历输入字符串 sfor (auto &i : s) {// 如果当前字符是字母或数字，则加入到 s_processed 中，并转为小写（数字则不变）if (isalnum(i)) {s_processed += tolower(i);}}// 设置左右指针，分别指向处理后字符串的开始和结束位置int left = 0, right = s_processed.size() - 1;// 使用双指针法进行比较while (left < right) {// 如果左右指针指向的字符不相同，则返回 falseif (s_processed[left] != s_processed[right]) {return false;}// 移动左右指针，继续向中间比较left++;right--;}// 如果所有字符都匹配，返回 truereturn true;}
};int main(int argc, char const *argv[])
{string str="0P";Solution s;if (s.isPalindrome(str)){cout<<"true";}else{cout<<"false";}return 0;
}

部分代码解读

//判断字符是否为字母或数字（返回0或1）
isalnum(i)
//将大写字母转换为小写字母，数字字符不变('1'转换后为‘1’)
tolower(i)

LeetCode 面试经典 150_双指针_验证回文串（25_125)原题链接
欢迎大家和我沟通交流(✿◠‿◠)