一、题目
给定一个字符串,验证它是否是回文串, 只考虑字母和数字字符 ,可以忽略字母的大小写。
说明: 本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man , a plan , a canal : Panama "
输出: true
示例 2:
输入: "race a car"
输出: false
二、解题思路
“回文串” 指的是正读和反读都相同的字符串,即其左右两边呈对称状态。要验证一个字符串是否为回文串,一种最简单的方式就是运用两个指针,一个从字符串前端开始,一个从后端开始,两个指针同时向中间移动。如果它们指向的字符不一样,那么这个字符串肯定不是回文字符串,直接返回 false 即可;如果这两个指针相遇了,那就直接返回 true。不过这道题只需要判断字母和数字,因为字符串中可能含有其他字符,对于这些其他字符我们只需跳过即可。下面画个图来看一下。
三、代码实现
#include <iostream>
#include <string>
#include <cctype>using namespace std;bool isPalindrome(string s) {int left = 0, right = s.length() - 1;while (left < right) {// left是左指针,如果不是字母和数字要过滤掉while (left < right && !isalnum(s[left]))left++;// right也一样,如果不是字母和数字也要过滤掉while (left < right && !isalnum(s[right]))right--;// 然后判断这两个字符是否相同,如果不相同直接返回false,这里是先把字符全部转化为小写if (tolower(s[left]) != tolower(s[right]))return false;// 如果left和right指向的字符忽略大小写相等的话,这两个指针要分别往中间移一步left++;right--;}// 如果都比较完了,说明是回文串,返回truereturn true;
}int main() {string s = "A man, a plan, a canal: Panama";bool result = isPalindrome(s);// 打印结果cout << "Input: \"" << s << "\"" << endl;cout << "Output: " << (result ? "true" : "false") << endl;return 0;
}
我们还可以在比较之前字母全部转化为小写,最外层改为for 循环的方式
#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>bool isPalindrome(std::string s) {// 先转为小写std::transform(s.begin(), s.end(), s.begin(), ::tolower);// 双指针法int i = 0, j = s.length() - 1;while (i < j) {// 跳过非字母和数字的字符while (i < j && !std::isalnum(s[i]))i++;while (i < j && !std::isalnum(s[j]))j--;// 比较字符if (s[i] != s[j])return false;// 移动指针i++;j--;}return true;
}int main() {std::string s = "A man, a plan, a canal: Panama";std::cout << std::boolalpha << isPalindrome(s) << std::endl; // 输出: truereturn 0;
}