[leetcode 面试经典 150 题] 25. 验证回声字符串 (C++)

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）

【题目描述】

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

【示例一】

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

【示例二】

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

【示例三】

输入：s = " " 输出：true 解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。 由于空字符串正着反着读都一样，所以是回文串。

【提示及数据范围】

• 1 <= s.length <= 2 * 10的5次方
• s 仅由可打印的 ASCII 字符组成

【代码】

// 方法一：筛选 + 翻转（判断回文串直接翻转字符串判断是否与原串相同即可）

// 在不翻转的情况下利用双指针也可以

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if ('a' <= ch && ch <= 'z' ||  'A' <= ch && ch <= 'Z' || ch >= '0' && ch <= '9') {
                sgood += tolower(ch);
            }
        }
        // 在变量名后直接加括号反转也是一种初始化方式
        string sgood_rev(sgood.rbegin(), sgood.rend());
        return sgood == sgood_rev;
    }
};

// 方法二：在原字符串上直接判断

// 每次将指针移到下一个字母字符或数字字符，再判断这两个指针指向的字符是否相同。

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