LeetCode 125 Valid Palindrome（有效回文）（*）

LeetCode 125 Valid Palindrome（有效回文）（*）

翻譯

給定一個字符串，確定它是否是回文的，僅僅考慮其中的數字和字符並忽略其他。

例如，
“A man, a plan, a canal: Pannama” 是回文的。
“race a car” 不是回文的

批注：
你是否考慮了字符串可能為空？這種面試的時候是一個好問題。

對於這問題的意圖，我們定義空字符串是回文的。

原文

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.

分析

題目解出來並不是很難，不過需要細心不過還是會出錯。

第一步就是要從原字符串中的干擾去掉，也就是只保留字母，這可以通過ascii來判斷。

然後構造出新的字符串，再判斷這個新字符串是否是回文的就好了。

然而我也還是錯了，首先我沒想清楚題目的例子，”aA”也是回文的。

再一次修改之後我還是錯了，因為題目的alphanumeric是字母數字均包含了，我一開始翻譯的就是字母，後來上文的翻譯也修改了。

於是我確定徹底的改革，將功能獨立出來，然而代碼好長了，但是很清晰：

代碼

class Solution {
public:
    bool isAlpha(char c) {
        int ascii = (int)c;
        if ((ascii >= 65 && ascii <= 90) || (ascii >= 97 && ascii <= 122))
            return true;
        else return false;
    }    
    bool isNumber(char c) {
        int ascii = (int)c;
        if (ascii >= 48 && ascii <= 57)
            return true;
        else return false;
    }       
    bool isAlphaAndNumber(char c1, char c2) {
        if ((isAlpha(c1) && isNumber(c2)) || (isAlpha(c2) && isNumber(c1)))
            return true;
        else return false;
    }       
    bool isPalindrome(string s) {
        if (s.size() == 0) return true;
        string newStr = "";
        for (int i = 0; i < s.size(); ++i) {
            // 只取出其中的字母和數字
            if (isAlpha(s[i]) || isNumber(s[i]))
                newStr += s[i];
        }
        for (int i = 0; i < newStr.size() / 2; ++i) {
            // 兩者一個是字母、一個是數字
            if (isAlphaAndNumber(newStr[i], newStr[newStr.size() - i - 1]))
                return false;
            // 兩者均為數字
            else if (isNumber(newStr[i]) && isNumber(newStr[newStr.size() - i - 1])) {
                // 判斷是否是同一個數字
                if (newStr[i] != newStr[newStr.size() - i - 1])
                    return false;
            }
            // 兩者均為字母
            else {
                // 前面判斷是否是同一個字母，後面判斷是否是互為大小寫
                if (newStr[i] != newStr[newStr.size() - i - 1] && abs((int)newStr[i] - (int)newStr[newStr.size() - i - 1]) != 32)
                    return false;
            }
        }
        return true;
    }                           
};

進階

一想到ascii就忘了還有toupper這些函數了，別人寫的……

class Solution {
public:
    bool isPalindrome(string s) {
        int l = 0, r = s.size() - 1;
        while(l <= r){
            while(!isalnum(s[l]) && l < r) l++;
            while(!isalnum(s[r]) && l < r) r--;
            if(toupper(s[l]) != toupper(s[r])) return false;
            l++, r--;
        }
        return true;
    }
};