美文网首页
[字符串]-125. 验证回文串

[字符串]-125. 验证回文串

作者: 追云的帆 | 来源:发表于2018-08-13 16:30 被阅读45次

    给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
    说明:本题中,我们将空字符串定义为有效的回文串。
    示例 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;
        }
    }
    

    相关文章

      网友评论

          本文标题:[字符串]-125. 验证回文串

          本文链接:https://www.haomeiwen.com/subject/fhyubftx.html