[leetcode]125-验证回文串

马谦马谦马谦

615
文章

17
评论

2020 年 3 月 29 日 15:11:42数据结构和算法评论286字数 571阅读 1 分 54 秒阅读模式

这道题本身是非常简单的，但是由于审题不仔细，忽略一个细节，导致提交了 6 次才成功，要检讨！

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/valid-palindrome

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

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

示例 1：

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

示例 2：

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

二、题解

思路：使用双指针，一个从前往后遍历，一个后从往前遍历。遇到非数字和字符就跳过，如果发现两个指针的字符不一样就返回 false，直到两个指针汇合，返回 true 。

要特别注意到的是回文串也包含了数字，我就是因为没看到还包含了数字，所以提交了 6 次才过。一直卡在测试案例"0P"上，注意是」零+P「，不是」欧+P「。因为 0 和 O 太像了，我看成了"OP"，本地测没问题，提交就有问题，最后失败了 5 次才发现，看评论区才知道大家都被这个输入坑了！！

[leetcode]125-验证回文串-图片1

三、代码

// 判断是否是字符或数字
bool isCharOrNum(char ch) {
    return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');
}

class Solution {
public:
    bool isPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            // 跳过非字符
            if (!isCharOrNum(s[j])) {
                j--;
                continue;
            }
            if (!isCharOrNum(s[i])) {
                i++;
                continue;
            }

            // 忽略大小写
            if (tolower(s[i]) != tolower(s[j]))
                return false;
            i++, j--;
        }
        return true;
    }
};

// 判断是否是字符或数字

bool isCharOrNum(char ch) {

return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9');

}

class Solution {

public:

bool isPalindrome(string s) {

int i = 0, j = s.size() - 1;

while (i < j) {

// 跳过非字符

if (!isCharOrNum(s[j])) {

j--;

continue;

}

if (!isCharOrNum(s[i])) {

i++;

continue;

}

// 忽略大小写

if (tolower(s[i]) != tolower(s[j]))

return false;

i++, j--;

}

return true;

}

};

单元测试：

#include <gtest/gtest.h>

TEST(leetcode, demo) {
    string s1("A man, a plan, a canal: Panama"), s2("race a car"), s3("OP");
    Solution s;
    EXPECT_TRUE(s.isPalindrome(s1));
    EXPECT_FALSE(s.isPalindrome(s2));
    EXPECT_FALSE(s.isPalindrome(s3));
}

TEST(leetcode, OP) {
    string s1("PO"), s2("0P");
    Solution s;
    EXPECT_FALSE(s.isPalindrome(s1));
    EXPECT_FALSE(s.isPalindrome(s2));
}

int main() {
    ::testing::InitGoogleTest();
    return RUN_ALL_TESTS();
}