leetcode 125. 验证回文串

题目描述:

给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。

说明:本题中,我们将空字符串定义为有效的回文串。

示例 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。

;