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; }};新聞熱點
疑難解答
