【5.8】指针算法-双指针验证回文串

一、题目

二、解题思路

        “回文串” 指的是正读和反读都相同的字符串，即其左右两边呈对称状态。要验证一个字符串是否为回文串，一种最简单的方式就是运用两个指针，一个从字符串前端开始，一个从后端开始，两个指针同时向中间移动。如果它们指向的字符不一样，那么这个字符串肯定不是回文字符串，直接返回 false 即可；如果这两个指针相遇了，那就直接返回 true。不过这道题只需要判断字母和数字，因为字符串中可能含有其他字符，对于这些其他字符我们只需跳过即可。下面画个图来看一下。

三、代码实现

#include <iostream>
#include <string>
#include <cctype>

using namespace std;

bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        // left是左指针，如果不是字母和数字要过滤掉
        while (left < right && !isalnum(s[left]))
            left++;
        // right也一样，如果不是字母和数字也要过滤掉
        while (left < right && !isalnum(s[right]))
            right--;
        // 然后判断这两个字符是否相同，如果不相同直接返回false，这里是先把字符全部转化为小写
        if (tolower(s[left]) != tolower(s[right]))
            return false;
        // 如果left和right指向的字符忽略大小写相等的话，这两个指针要分别往中间移一步
        left++;
        right--;
    }
    // 如果都比较完了，说明是回文串，返回true
    return true;
}

int main() {
    string s = "A man, a plan, a canal: Panama";
    bool result = isPalindrome(s);

    // 打印结果
    cout << "Input: \"" << s << "\"" << endl;
    cout << "Output: " << (result ? "true" : "false") << endl;

    return 0;
}

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>

bool isPalindrome(std::string s) {
    // 先转为小写
    std::transform(s.begin(), s.end(), s.begin(), ::tolower);

    // 双指针法
    int i = 0, j = s.length() - 1;
    while (i < j) {
        // 跳过非字母和数字的字符
        while (i < j && !std::isalnum(s[i]))
            i++;
        while (i < j && !std::isalnum(s[j]))
            j--;

        // 比较字符
        if (s[i] != s[j])
            return false;

        // 移动指针
        i++;
        j--;
    }
    return true;
}

int main() {
    std::string s = "A man, a plan, a canal: Panama";
    std::cout << std::boolalpha << isPalindrome(s) << std::endl;  // 输出: true
    return 0;
}