原文链接: https://leetcode-cn.com/problems/XltzEq

中文题目

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

本题中，将空字符串定义为有效的 回文串 。

 

示例 1:

输入: s = "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: s = "race a car"
输出: false
解释："raceacar" 不是回文串

 

提示：

• 1 <= s.length <= 2 * 105
• 字符串 s 由 ASCII 字符组成

 

注意：本题与主站 125 题相同： https://leetcode-cn.com/problems/valid-palindrome/

通过代码

高赞题解

回文解释

柳庭风静人眠昼，昼眠人静风庭柳。
香汗薄纱凉，凉纱薄汗香。
手红水碗藕，藕碗水红手。
郎笑藕丝长，长丝藕笑郎。————— 苏轼《菩萨蛮》

思路

判断一个字符串是不是回文，常用的方法就是使用双指针。第一个指针从第一个字符向后移动，第二个指针从最后一个字符向前移动。若当前指针所指字符相同，则判断下一对字符，直到两个指针相遇。因为本题中只判断字母与数字，所以指针遇到其他字符则跳过。另外字母不区分大小写，则可以都转化为大写或者小写字母判断。

介绍几个比较有用的函数：

• isalpha ：判断一个字符是否为字母，如果是则返回true，否则返回false；
• isdigit : 判断一个字符是否表示数字，如果是则返回true，否则返回false；
• isalnum : 判断一个字符是否表示数字或者字母，如果是则返回true，否则返回false;
• islower : 判断一个字符是否为小写字母，如果是则返回true，否则返回false;
• isupper : 判断一个字符是否为大写字母，如果是则返回true，否则返回false；
• tolower : 若字符为字母则转化为小写字母；
• toupper : 若字符为字母则转化为大写字母；

代码如下，时间复杂度为 O(n)，空间复杂度为 O(1)。

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        while (i < j) {
            if (!isalnum(s[i])) {
                i++;
            }
            else if (!isalnum(s[j])) {
                j--;
            }
            else {
                if (tolower(s[i]) != tolower(s[j])) {
                    return false;
                }
                else {
                    i++;
                    j--;
                }
            } 
        }
        return true;
    } 
};

统计信息

通过次数	提交次数	AC比率
7340	14165	51.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言