LeetCode 125. Valid Palindrome

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 125. Valid Palindrome 原题链接简单

作者：

yxc , 2018-05-29 02:36:34 , 所有人可见 , 阅读 2295

4

2

题目描述

给定一个字符串，判断它是否是回文串。仅考虑大小写字母和数字，忽略其他字符。

注意：规定空字符串也是回文串。在这道题目中，小写字母可以和大写字母匹配，例如 'a' 和 'A' 算相等。

样例1

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

样例2

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

算法

(线性扫描) $O(n)$

用两个指针分别从前后开始，往中间扫描。
每次迭代两个指针分别向中间靠近一步，靠近的过程中忽略除了字母和数字的其他字符。
然后判断两个指针所指的字符是否相等，如果不相等，说明不是回文串。
当两个指针相遇时，说明原字符串是回文串。

时间复杂度分析：每个字符仅会被扫描一次，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    bool check(char c)
    {
        return c >= '0' && c <= '9' || c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z';
    }

    bool isPalindrome(string s) {
        int i = 0, j = (int)s.size() - 1;
        while (i < j)
        {
            while (i < j && !check(s[i])) i ++ ;
            while (i < j && !check(s[j])) j -- ;
            if (s[i] != s[j] && s[i] != (s[j]^32)) return false;
            i ++, j --;
        }
        return true;
    }
};

12 评论

小雨 2018-11-26 05:25

可是为什么是亦或呢？

yxc 2018-11-26 15:58

和大小写字母的Ascii码的二进制表示有关。在相同字母的大小写的二进制表示里，只有第5位不同，异或32可以起到只改变第5位的效果，从而实现大小写的转化。

alin 2020-07-15 10:24 回复了 yxc 的评论

666

高小呆 2020-10-12 17:48 回复了 yxc 的评论

直接写+32，也可以吧，这两个有什么不一样的吗

yxc 2020-10-14 16:09 回复了高小呆的评论

没啥不一样。不过这样有时候要加32，有时候要减32，要区分一下。

高小呆 2020-10-15 15:47 回复了 yxc 的评论

好的，谢谢y总，yyds

明天去你那玩 2021-12-27 20:22

class Solution
{
public:
bool validPalindrome(string s)
{
int n = s.size();
int l = 0;
int r = n - 1;
while (l < r)
{
if (s[l] != s[r])
return check(s, l + 1, r) || check(s, l, r - 1);
l ++;
r –;
}
return true;
}

bool check(string & s, int lo, int hi)
{
    while (lo < hi)
    {
        if (s[lo] != s[hi])
            return false;
        lo ++;
        hi --;
    }
    return true;
}

};

作者：Hanxin_Hanxin
链接：https://leetcode-cn.com/problems/RQku0D/solution/cpython3java-shuang-zhi-zhen-by-hanxin_h-0ucb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。