题目描述:
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama" 输出: true
思路:
用两个指针p和q,p从前往后移动,q从后往前移动。如果不是字母或数字,则忽略;否则停止移动,并且把大写字母都转换成小写字母,然后比较p和q的内容是否相同。重复这个过程直到p、q相遇。
代码:
//判断字符a是不是字母,并转换大小写。
inline bool OK(char &a)
{
//大写字母比小写字母小32,二进制第6位是0
if('A'<=a && a<='Z')
a=a|32;
if(('a'<=a && a<='z')||('0'<=a && a<='9'))
return true;
return false;
}
//验证回文串
bool isPalindrome(string s) {
if(s.size()==0) return true;
auto p=s.begin(),q=s.end()-1;
while(p<q)
{
while(!OK(*p)) p++;
while(!OK(*q)) q--;
if(p<q && *p!=*q)
return false;
p++,q--;
}
return true;
}
时间复杂度是O(n),空间复杂度O(1),测试运行时间 8ms。
;