LeetCode 125. 验证回文串 题解

题目链接:125. 验证回文串

题目类型:双指针

思路:

1. 题目要求忽略字母大小写,我们可以先遍历一遍字符串 s,把所有大写字母转换为小写字母。

2. 题目要求只考虑数字和字母是否为回文,所以我们需要多次判断某个字符是否为数字和字母,在代码中封装了两个函数,分别做这两件事。

3. 我们用 l, r 两个指针,分别从字符串两侧向中间行进。如果找到了两个数字或字母字符,我们比较这两个字符是否相同。若不相同说明不是回文串,直接 return false。如果遍历完全部字符串,说明是回文串,返回 true

class Solution {
public:
    bool isnum(char c) {
        // 判断是否为数字字符
        return c >= '0' && c <= '9';
    }

    bool isalpha(char c) {
        // 判断是否为字母字符
        return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
    }

    bool isPalindrome(string s) {
        int n = s.size();

        for(char &c : s) {
            if(c >= 'A' && c <= 'Z') c = c - 'A' + 'a';
        }

        int l = 0, r = n - 1;
        while(l < r) {
            while(l < r && !isnum(s[l]) && !isalpha(s[l])) l++;
            while(l < r && !isnum(s[r]) && !isalpha(s[r])) r--;
            if(l >= r) break;
            if(s[l] != s[r]) return false;
            l++, r--;
        }
        return true;
    }
};

上一篇:位运算 看这篇就够了


下一篇:Leetcode Algorithm-125. 验证回文串