使用雙指標在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)，常數空間