给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
说明:本题中,我们将空字符串定义为有效的回文串。
示例 1:
输入: "A man, a plan, a canal: Panama"
输出: true
示例 2:
输入: "race a car"
输出: false
解析:
验证回文串比较常见。回文串就是正反读都一样,例如:"level","noon"
。这里加入了空格和数字进行混合。
只需要建立两个指针,left和right分别从字符的开头和结尾处开始遍历整个字符串,如果遇到非字母非数字的字符就跳过,继续向下一个,直到找到下一个或者遍历结束。如果遇到大写字母,就将其转换为小写字母。左右指针同时找到数字或者字母,进行比较,若相同,继续向下遍历;若不同,则返回false。
时间复杂度为 o(n);
Java代码
class Solution {
public boolean isTure(char c){
if(c>='a'&&c<='z') return true;
if(c>='A'&&c<='Z') return true;
if(c>='0'&&c<='9') return true;
return false;
}
public boolean isPalindrome(String s) {
//两个指针 left right
//1.遇到大写换成小写 2.遇到非字母数字的字符跳过
char[] ss = s.toCharArray();
int left = 0;
int right = s.length()-1;
while(left<right){
if(!isTure(ss[left])){
left++;
}
else if(!isTure(ss[right])){
right--;
}
else if(((ss[left]+32-'a')%32)!=((ss[right]+32-'a')%32)){//直接求余会出现问题 如 '0'和'P'求余的值相同
return false;
}
else{
left++;
right--;
}
}
return true;
}
}
网友评论