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” is not a 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.
s思路： 1. 确实没想到给定的string如果是空的话，怎么算？这个不周全的考虑，其实是思维上的不到位，思维的层次还不够，只考虑问题如何解决？没考虑问题的具体范围，也就是说没有花时间去观察问题的边界在哪儿，不考虑边界，对问题的界定和认知就不清楚不明确。这就是思维的程度还不够高，对基本问题忽略所致！ 2. 回到问题上，这个题的边界就是string的最小长度为0的情况。 3. 这个问题如果是一串只有小写字母的string就很好判断，例如:abcba，因为极其规则、极其美观的结构，所以很容易就做了。这个题给的string就很不规则，例如：”A man, a plan, a canal: Panama”，有空格，有符号，有大小写。不过看到这种情况，也不必惊恐，不知如何是好，或者说不知如何是好也没什么，但且不要被这种惊恐和不知所措的情绪笼罩，而不能继续深入去思考解答方法。 4. 不规则的情况，就需要两个指针。一个放在左边，一个放在右边，去跟踪大小写字母的位置，当两个指针都恰好指向了大小写字母，就比较是否相等或相差为26：如果是，则都移动一位，进行下一个比较。
//方法1：有bug，而且代码冗长。利用现成的函数：isalnum()判断char是否是数字或字母。//大小写字母如何对应？都转换成toupper()或者tolower()class Solution {public: bool isPalindrome(string s) { // int l=0,r=s.size()-1; while(l<r){ if((s[l]>='a'&&s[l]<='z'||s[l]>='A'&&s[l]<='Z'||s[l]>='0'&&s[l]<='9')&&(s[r]>='a'&&s[r]<='z'||s[r]>='A'&&s[r]<='Z'||s[r]>='0'&&s[r]<='9')){ if(s[l]==s[r]||abs(s[l]-s[r])==32){//bug：当s[l]='0',s[r]='P'，也出现abs(s[l]-s[r])==32。 l++;r--; }else return false; }else if((s[l]>='a'&&s[l]<='z'||s[l]>='A'&&s[l]<='Z'||s[l]>='0'&&s[l]<='9')) r--; else if (s[r]>='a'&&s[r]<='z'||s[r]>='A'&&s[r]<='Z'||s[r]>='0'&&s[r]<='9') l++; else {r--;l++;} } return true; }};//方法2：用isalnum()判断char是否是数字或字母；大小写转换用toupper()或者tolower()//代码的if-else还可以简化，看方法3class Solution {public: bool isPalindrome(string s) { // int l=0,r=s.size()-1; while(l<r){ if(isalnum(s[l])&&isalnum(s[r])){ if(tolower(s[l])!=tolower(s[r])) return false; l++;r--; }else if(!isalnum(s[l])) l++; else if(!isalnum(s[r])) r--; else {l++;r--;} } return true; }};//方法3：方法2基础上优化。简化if-else，代码清楚不含糊。class Solution {public: bool isPalindrome(string s) { // int l=0,r=s.size()-1; while(l<r){ if(!isalnum(s[l])) l++; if(!isalnum(s[r])) r--; if(isalnum(s[l])&&isalnum(s[r])){ if(tolower(s[l])!=tolower(s[r])) return false; l++;r--; } } return true; }};新闻热点
疑难解答
