125 Valid Palindrome 驗(yàn)證回文串

Description:
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:

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

Example 2:
Input: "race a car"
Output: false

題目描述:
給定一個(gè)字符串，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符，可以忽略字母的大小寫。

說(shuō)明：本題中，我們將空字符串定義為有效的回文串。

示例:

示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true

示例 2:
輸入: "race a car"
輸出: false

思路:

利用ASCII值比較, 留下小寫字母和數(shù)字, 大寫字母轉(zhuǎn)換為小寫字母
雙指針?lè)? 設(shè)置一對(duì)指針?lè)謩e指向字符串開始和結(jié)束位置, 分別移動(dòng)兩個(gè)指針比較
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)

雙指針?lè)?two pointers

一般是指設(shè)置快慢指針或者兩個(gè)指針?lè)謩e指向數(shù)組(字符串)的開頭和結(jié)尾, 分別進(jìn)行掃描, 以期達(dá)到時(shí)間復(fù)雜度為 O(n)的方法
這種類型的題目通常都有特殊條件限制:

1. 回文
2. 對(duì)稱
3. 遞增/遞減

應(yīng)用

1. 鏈表的中點(diǎn): 快慢指針
2. 鏈表的環(huán): 快慢指針
3. 求回文串: 頭尾指針
4. 奇偶分別排序/插入: 頭尾指針

代碼:
C++:

class Solution 

public:
    bool isPalindrome(string s) 
    {
        int i = 0, j = s.size() - 1;
        while (i < j) 
        {
            // isalnum(char c) 用來(lái)判斷一個(gè)字符是否為英文字母或數(shù)字，相當(dāng)于 isalpha(c) || isdigit(c)
            // isalpha(char c) 用來(lái)判斷一個(gè)字符是否是英文字母，相當(dāng)于 isupper(c) || islower(c)
            while (i < j and !isalnum(s[i])) i++;
            while (i < j and !isalnum(s[j])) j--;
            // toupper(char c) 如果c為小寫英文字母，則返回對(duì)應(yīng)的大寫字母；否則返回原來(lái)的值。
            // tolower(char c) 如果c為大寫英文字母，則返回對(duì)應(yīng)的小寫字母；否則返回原來(lái)的值。
            if (tolower(s[i++]) != tolower(s[j--])) return false;
        }
        return true;
    }
};

Java:

class Solution {
    public boolean isPalindrome(String s) {
        if (s == null) return true;
        s = s.toLowerCase();
        int i = 0, j = s.length() - 1;
        while (i < j) {
            while (i < j && !isLegal(s.charAt(i))) i++;
            while (i < j && !isLegal(s.charAt(j))) j--;
            if (s.charAt(i++) != s.charAt(j--)) return false;
        }
        return true;
    }

    private boolean isLegal(char c) {
        return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
    }
}

Python:

class Solution:
    def isPalindrome(self, s: str) -> bool:
        return ''.join(filter(str.isalnum, s)).lower() == ''.join(filter(str.isalnum, s)).lower()[::-1]