LeetCode 125. Valid Palindrome [Easy] [C++] 解題筆記

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

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

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

想法:

    這題就直接同時從頭與從尾端依序比較第一個與第n個字元是否相等，一直遍歷到中間的字元為止，這期間只要用不符合

的情況就可以直接 return false了。另外因為字串中還是有可能會包含不需要考慮的字元要記得過濾掉(ex: 空格)。

因為大小寫的英文字母視為一樣的，因此在比較之前可以先將所有字母都轉換成小寫再進行比較。

Complexity: O(n) time

完整程式碼:

class Solution {
public:
    bool isAlphanumeric(char& c) {
        if (c >= 'a' && c <= 'z') { return true; }
        if (c >= 'A' && c <= 'Z') { return true; }
        if (c >= '0' && c <= '9') { return true; }
        return false;
    }       
    bool isPalindrome(string s) {
        int left = 0;
        int right = s.size() - 1;
        while (left < right) {
            if (!isAlphanumeric(s[left])) { ++left; }
            else if (!isAlphanumeric(s[right])) { --right; }
            else if ((s[left] + 32 - 'a') % 32 != (s[right] + 32 - 'a') % 32) {
                //cout<<s[left]<<" "<<s[right]<<endl;
                return false;
            }
            else {
                ++left;
                --right;
            }
        }
        return true;
    }
};