125. Valid Palindrome


Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama"is a palindrome.
"race a car"isnota palindrome.

Note:
Have you consider that the string might be empty? This is a good question to ask during an interview.

For the purpose of this problem, we define empty string as valid palindrome.

题目大意：

回文的检测。

思路：

1.清洗字符串，得到只有数字和字母的字符串。

2.通过比较首尾的字符来判断。

代码如下：

classSolution{public:vector<string>stringSplit(strings,constchar*split){vector<string>result;constintsLen=s.length();char*cs=newchar[sLen+1];strcpy(cs,s.data());char*p;p=strtok(cs,split);while(p){printf("%s\n",p);stringtmp(p);result.push_back(tmp);p=strtok(NULL,split);}returnresult;}boolisPalindrome(strings){if(s.size()==0||s.size()==1)returntrue;vector<string>vecStrs=stringSplit(s,"~!@#$%^&*().,:;-?\"'`");s="";for(inti=0;i<vecStrs.size();i++)s+=vecStrs[i];if(s.size()==1||s.size()==0)returntrue;inti=0;for(;i<s.size()/2;i++){if(s[i]<=57||s[s.size()-i-1]<=57){if(s[i]==s[s.size()-i-1]){continue;}else{returnfalse;}}elseif(s[i]==s[s.size()-i-1]||s[i]-s[s.size()-i-1]==32||s[s.size()-i-1]-s[i]==32){continue;}else{returnfalse;}}returntrue;}};


上面的做法效率低下，还有对API不熟悉。

下面是对上面的改进：

参考https://discuss.leetcode.com/topic/48376/12ms-c-clean-solution

代码如下：

classSolution{public:boolisPalindrome(strings){inti=0,j=s.size()-1;while(i<j){while(!isalnum(s[i])&&i<j)i++;while(!isalnum(s[j])&&i<j)j--;if(tolower(s[i++])!=tolower(s[j--]))returnfalse;}returntrue;}};

这里使用了isalnum()函数来判断是否为文字数字。

通过使用tolower()来统一字符的大小写，都变为小写。


2016-08-11 13:26:25