验证回文串1

1.题目：125. 验证回文串 - 力扣（LeetCode）

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

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

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

2.解题思路

去除特殊字符，如标点符号和空格，仅保留英文字母和阿拉伯数字，并且大写变小写。

这里需要借助于c++的库函数，有如下几个：

1. isalnum(ch)：检查字符 ch 是否是字母或数字。返回0（即为假）或非零值（真）。
2. tolower(ch)：将大写字母转换为小写。如果字符不是大写字母，则返回原字符。toupper，小写变大写。
3. string sgood_rev(sgood.rbegin(), sgood.rend())：翻转字符串sgood为sgood_rev。使用了 rbegin() 和 rend()，用于获取反向迭代器。直接当成反转字符串的方法用即可。

3.参考代码

解法一

class Solution {
public:bool isPalindrome(string s) {// 先去除空格以及标点符号,并将大写字母转为小写string sgood;for (char c : s) {if (isalnum(c)) {sgood += tolower(c);}}// 得到清理后的字符串后再进行翻转string sgood_rev(sgood.rbegin(), sgood.rend());return sgood == sgood_rev;}
};

解法二：双指针

 

class Solution {
public:bool isPalindrome(string s) {// 双指针int L = 0;int R = s.size() - 1;while (L <= R) {// 跳过特殊字符while (!isalnum(s[L]) && L <= R) {L++;}while (!isalnum(s[R]) && L <= R) {R--;}// 比较对称位置元素if (L <= R) { // 再次判断if (tolower(s[L]) != tolower(s[R])) {return false;}L++;R--;}}return true;}
};

在用解法二做题时，遇到了 SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior ，说明发生了地址越界错误！！！这个一定要注意！可以用空字符串为例，进行思考。

另外一个错误就是，跳过特殊字符时也需要进行循环处理。

错误代码如下：

class Solution {
public:bool isPalindrome(string s) {// 双指针int L = 0;int R = s.size() - 1;while (L <= R) {// 跳过特殊字符if (!isalnum(s[L])) {L++;}if (!isalnum(s[R])) {R--;}// 比较对称位置元素if (tolower(s[L]) != tolower(s[R])) {return false;}L++;R--;}return true;}
};