题目描述

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true

示例 2:

输入: "race a car"
输出: false

我的解法——修改字符串后遍历（AC）

遍历字符串，将数字和字母提取出来一个新的字符串，然后遍历新的字符串来判断是否是回文串。
时间空间复杂度均为O(n)。
Beat44%

class Solution:
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        length = len(s)
        s = s.lower()
        ss = s
        s = ''
        for now in ss:
            if((now >= 'a' and now <= 'z') or(now >= 'A' and now <= 'Z') or (now >= '0' and now <= '9')):
                s += now
        length = len(s)
        for i in range(int(length/2)):
            if(s[i] != s[length - i - 1]):
                return False
        return True

最优解法——双指针遍历

定义两个指针 L, R,分别从开始和最后的点开始遍历，每次取符合条件的字符，然后判断，这样没有额外的空间复杂度
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    bool isPalindrome(string s) {
        int len = s.length();
        int l = 0, r = len - 1;
        while(l < r){
            while(l < r){
                if((s[l] >= 'a' && s[l] <= 'z') || (s[l] >= '0' && s[l] <= '9') || (s[l] >= 'A' && s[l] <= 'Z')){
                    if(s[l] >= 'A' && s[l] <= 'Z'){
                        s[l] = s[l] - 'A' + 'a';
                    }
                    break;
                }
                l++;
            }
            while(r > l){
                if((s[r] >= 'a' && s[r] <= 'z') || (s[r] >= '0' && s[r] <= '9') ||(s[r] >= 'A' && s[r] <= 'Z')){
                    if(s[r] >= 'A' && s[r] <= 'Z'){
                        s[r] = s[r] - 'A' + 'a';
                    }
                    break;
                }
                r--;
            }
            if(s[l] != s[r]){
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
};