使用双指针在C++中检查给定字符串是否为回文

---

回文是指一个单词、短语、数字或其他字符序列，从前后两个方向读取都相同。在字符串中，回文字符串是可以从左到右和从右到左读取都相同的字符串。在这篇文章中，我们将学习如何使用双指针技术在C++中检查给定字符串是否为回文。

问题

给定一个字符串，我们必须使用C++中的双指针方法检查它是否为回文。

示例 1

输入： "abcba"

输出： True

解释

"abcba" 是一个回文，因为它正反读都相同，反转后与原始字符串相同或一致。

示例 2

输入： "ayush"

输出： False

解释

"ayush" 不是回文，因为它正反读不相同，反转后与原始字符串不相同或不一致。

示例 3

输入： "Abcba"

输出： False

解释

"Abcba" 不是回文，因为它正反读不相同，除非你明确忽略大小写差异，否则此比较区分大小写。

使用双指针的解决方案

双指针技术是一种流行的算法，用于解决涉及序列（如数组或字符串）的问题。它是帮助降低时间复杂度并使解决方案更有效、更容易理解的方法之一。在这种方法中，我们使用两个指针：一个从开头，另一个从结尾。我们将左指针设置在字符串的开头（索引 0），将右指针设置在字符串的结尾（长度 - 1）。我们将比较左右位置的字符，直到左指针不再小于右指针。如果在任何位置字符不相等，则返回 false。如果它们相等，则我们将左指针向前移动一个位置，将右指针向后移动一个位置。

步骤

• 设置两个指针：左指针和右指针。左指针从字符串的开头（索引 0）开始，右指针从字符串的结尾（长度 - 1）开始。
• 运行循环，直到左指针小于右指针。如果字符相等，则将左指针向前移动一个位置，将右指针向后移动一个位置。继续此过程，直到左指针与右指针相遇或超过右指针。
• 循环完成后返回 true。

实现

#include <bits/stdc++.h>
using namespace std;

bool stringPalindrome(string str) {
    int left = 0;
    int right = str.size() - 1;

    while (left < right) {
        if (str[left] != str[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

int main() {
    string input;
    cout << "Enter a string: "<< endl;
    cin >> input;

    if (stringPalindrome(input)) {
        cout << "The string is a palindrome." << endl;
    } else {
        cout << "The string is not a palindrome." << endl;
    }
    return 0;
}

输出

Enter a string:
aba
The string is a palindrome.

时间复杂度：O(n)，因为我们遍历了一半的字符串。

空间复杂度：O(1)，常数空间