每日一练（40）：验证回文串

---

title: 每日一练（40）：验证回文串

categories:[剑指offer]

tags:[每日一练]

date: 2022/04/12

---

每日一练（40）：验证回文串

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

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

示例 1:

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

输出: true

解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"

输出: false

解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105

字符串 s 由 ASCII 字符组成

来源：力扣（LeetCode）

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

方法一：字符串预处理 + 双指针

思路分析

isalnum：判断字符变量c是否为字母或数字，若是则返回非零，否则返回零。

tolower：把字母字符转换成小写，非字母字符不做出处理

1.先把字符串s做处理

2.双指针判断，左指针指向第一个位置，右指针指向最后一个位置，依次判断是否相同

bool isPalindrome(string s) {
    string str;
    for (const char &ch : s) {
        if (isalnum(ch)) {
            str.push_back(tolower(ch));// 将数字和字母保存在 str 中，大写字母转换成小写
        }
    }
    // 左指针指向第一个位置，右指针指向最后一个位置
    // 依次比较是否相同
    int l = 0, r = str.size() - 1;
    while (l < r) {
        if (str[l] != str[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

方法二：筛选 + 判断

思路分析

对字符串 s 进行一次遍历，并将其中的字母和数字字符进行保留，放在另一个字符串 sgood 中。这样我们只需要判断 sgood 是否是一

个普通的回文串即可

使用语言中的字符串翻转 API 得到 sgood 的逆序字符串 sgood_rev

bool isPalindrome(string s) {
    string sgood;
    for (const char &ch : s) {
        if (isalnum(ch)) {
            sgood.push_back(tolower(ch));// 将数字和字母保存在 sgood 中，大写字母转换成小写
        }
    }
    string sgood_rev(sgood.rbegin(), sgood.rend());// API逆转字符串
    return sgood == sgood_rev;
}