首页 > 代码库 > leetcode:Valid Palindrome

leetcode:Valid Palindrome

一、     题目

题目给出一个字符串,求出它是否为回文字符串,其中只有字母和数字是有效字符,其他的字符可以忽略。

例如:"Aman, a plan, a canal: Panama" 是回文字符串.

"race a car" is not a palindrome.不是回文字符串

二、     分析

看到这个题目我首先想到的是使用两个数组将有效字符串保存,其中一个正序一个逆序,然后做比较。但是考虑到效率和空间使用,可以使用“两指针法”,即设置一个左指针一个右指针,相向移动,判断他们的有效值是否相等,不相等则直接false,直到相遇。


class Solution {
public:
	//判断字符是不是字母或字符 
	bool isAlphanumeric(char c)
     {
         if((c >= 'a' && c <= 'z')||(c >= 'A' && c <= 'Z')||(c >= '0' && c <= '9'))
             return true;
         else return false;
     }
    bool isPalindrome(string s) {
        
        int len = s.size();
        //判断是否为空,为空则返回真 
        if(len == 0) return true;
        int left=0;
        int right = len-1;
        while(left<right){
        	//注意判断left是否小于len,当时就卡在这了 
        	if(!isAlphanumeric(s[left])&&left<=len-1){
        		left++;
        	}
        	else if(!isAlphanumeric(s[right])&&right>=0){
        		right--;
        	}
        	else {
        		//注意字母的大小写,这里只需要判断字母是否相等或差的绝对值是否为32 
        		if(s[left] != s[right]&&fabs(s[left]-s[right])!=32)
        			return false;
        		left++;
        		right--;
			}
        }
        return true;
    }
};


leetcode:Valid Palindrome