题目:验证回文串
思路:
这段代码是一个判断字符串是否为回文的函数。它接受一个 string 类型的参数 s,并依次执行两个步骤:
首先对字符串进行预处理:
- 将大写字母转换成小写字母;
- 移除非字母数字字符。
然后再用双指针方法检查回文性:
- 定义左右指针
left
和right
分别指向字符串的头和尾; - 如果左右指针对应的字符是否相等,则将左指针右移、右指针左移,并继续比较;
- 直到左指针和右指针相遇或者穿过来确定整个字符串是否是回文。
其中,预处理部分中关于大写和小写字母的转换是通过 ASCII 码计算完成的,将大写字母的码值加上 32 后即为对应小写字母的码值。移除非字母数字字符采用了 C++ 中的 erase 函数删除。而在回文判断时,因为该题中要求不区分大小写,所以在取出每一个字符时都会先将其转化成小写形式。
错误实现:
bool my_isalpha(char s)
{if ((s >= 'a' && s <= 'z') || (s >= 'A' && s <= 'Z')){return true;}else{return false;}
}bool my_isdigit(char s)
{if (s >= '0' && s <= '9'){return true;}else{return false;}
}class Solution {
public:bool isPalindrome(string s){//下标int i = 0;//遍历:while (i < s.size()){//大写字母转小写if (s[i] >= 'A' && s[i] <= 'Z'){s[i] = s[i] + 32;i++;}//非字母数字移除else if (!my_isalpha(s[i])&&!my_isdigit(s[i])){//从该下标开始依次往前挪1int j = i;while (j < s.size()){s[j] = s[j + 1];j++;}i++;}//小写字母、数字else{i++;}}//首尾同时遍历,检查是否恒等int left = 0;int right = s.size() - 1;while (left < s.size() - 1 && right >= 0){char head = s[left];char tail = s[right];if (head != tail){return false;}else{left++;right--;}}//遍历结束,都没有出差return true;}
};
错误原因:
在您的代码中,处理非字母数字字符的部分只是将其从字符串中移除了,并没有进行特殊处理即删除操作。这样在一些特定的输入字符串下会导致结果错误。
例如,当输入为 "A man, a plan, a canal: Panama"
时,经过第一个 while 循环处理后,字符串变为 "amanaplanacanalpanama"
。此时再进行回文判断会得到不正确的答案,因为原本应该从一个空格或标点符号开始的字母可能被移动到前面或后面,使得判断出错。
因此,在处理非字母数字字符的过程中,应该采用删除该字符并保持下标不变的方式,具体的实现上可以使用 C++ 中的 erase()
函数。另外,您的回文判断也存在问题,初始化 left
应该为 0 而不是 1。下面是修改后的代码:
正确实现:
class Solution {
public:bool isPalindrome(string s){//下标int i = 0;//遍历:while (i < s.size()){//大写字母转小写if (s[i] >= 'A' && s[i] <= 'Z'){s[i] = s[i] + 32;i++;}//非字母数字移除else if (!isalnum(s[i])){s.erase(i, 1);}//小写字母、数字else{i++;}}//首尾同时遍历,检查是否恒等int left = 0;int right = s.size() - 1;while (left < right){char head = s[left];char tail = s[right];if (head != tail){return false;}else{left++;right--;}}//遍历结束,都没有出差return true;}
};