在給定的字串陣列中查詢所有迴文字串

---

在這個問題中，我們需要從給定的陣列中找到所有迴文字串。如果一個字串從開頭到結尾讀取都相同，則稱該字串為迴文。

我們可以使用兩種方法來檢查字串是否為迴文。在第一種方法中，我們反轉字串並將其與原始字串進行比較，在第二種方法中，我們不斷比較字串的字元從開頭到結尾。

問題陳述 - 我們給定一個包含 N 個字串的陣列。我們需要列印陣列中所有是迴文的字串。如果陣列不包含任何迴文字串，則列印 -1。

示例

輸入

array[] = {"tut", "point", "tutorial", "nanan", "great"}

輸出

tut, nanan

解釋 - 給定陣列中的 'tut' 和 'nanan' 是迴文字串。

輸入

 array[] = {"point", "tutorial", "shubham", "great"}

輸出

-1

解釋 - 陣列不包含任何迴文字串，因此列印 -1。

輸入

 array[] = {}

輸出

-1

解釋 - 陣列為空，因此列印 -1。

方法 1

在這種方法中，我們遍歷陣列並檢查特定字串是否為迴文。我們將使用 reverse() 方法來檢查字串是否為迴文。

演算法

步驟 1 - 定義 'palindromes' 列表以儲存所有迴文字串。

步驟 2 - 遍歷陣列。

步驟 3 - 執行 checkForPalindrome() 函式以檢查第 p 個索引處的字串是否為迴文。

步驟 3.1 - 在函式中將字串儲存到 'temp' 字串中。

步驟 3.2 - 使用 reverse() 方法反轉 alpha 字串。

步驟 3.3 - 在比較 temp 和 alpha 後返回布林值。

步驟 4 - 如果特定字串是迴文，則將其推入 'palindromes' 列表。

步驟 5 - 返回 palindromes 列表。

示例

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

bool checkForPalindrome(string &alpha) {
    // Copy the string
    string temp = alpha;
    // Reverse the string
    reverse(alpha.begin(), alpha.end());
    // If the string and its reverse is equal, return true. Else return false.
    return temp == alpha;
}
vector<string> FindAllPalindrome(string array[], int N) {
    vector<string> palindromes;
    // traverse the array
    for (int p = 0; p < N; p++) {
        // If the string is a palindrome, push it into vector
        if (checkForPalindrome(array[p])) {
            palindromes.push_back(array[p]);
        }
    }
    return palindromes;
}
int main() {
    string array[] = {"tut", "point", "tutorial", "nanan", "great"};
    int N = sizeof(array) / sizeof(array[0]);
    // Print the required answer
    vector<string> list = FindAllPalindrome(array, N);
    if (list.size() == 0)
        cout << "-1";
    else {
        cout << "The palindrome strings from the given array are : ";
        for (string str : list) {
            cout << str << ", ";
        }
    }
    return 0;
}

輸出

The palindrome strings from the given array are : tut, nanan,

時間複雜度 - O(N*K)，其中 N 是陣列長度，K 是字串的最大長度。

空間複雜度 - O(N + K)，因為我們將原始字串儲存到 'temp' 字串中，並將迴文字串儲存在列表中。

方法 2

在這種方法中，我們直接列印迴文字串，而不是將它們儲存在列表中。此外，我們匹配字串從開頭到結尾的字元以檢查字串是否為迴文，而不是使用 reverse() 方法。

演算法

步驟 1 - 將 'palCnt' 變數初始化為 0 以儲存陣列中迴文字串的數量。

步驟 2 - 遍歷字串並執行 checkForPalindrome() 函式，並將字串作為引數傳遞以檢查字串是否為迴文。

步驟 2.1 - 在 checkForPalindrome() 函式中初始化 left 和 right 變數。

步驟 2.2 - 繼續遍歷字串，直到 left 小於 right。

步驟 2.3 - 如果 left 和 right 索引處的字元不同，則返回 false。

步驟 2.4 - 將 left 增加 1，並將 right 減小 1。

步驟 2.5 - 最後，返回 true。

步驟 3 - 如果第 p 個索引處的字串是迴文，則將 'palCnt' 的值增加 1，並列印字串。

步驟 4 - 最後，如果 'palCnt' 的值為 0，則列印 -1。

示例

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

bool checkForPalindrome(string &alpha) {
    // Initialize the start and end index
    int left = 0;
    int right = alpha.length() - 1;
    // traverse the string
    while (left < right) {
        // compare characters from start and end
        if (alpha[left] != alpha[right]) {
            return false;
        }
        // change value of pointers
        left++;
        right--;
    }
    return true;
}
void FindAllPalindrome(string array[], int N) {
    int palCnt = 0;
    // traverse the array
    for (int p = 0; p < N; p++) {
        // If the string is palindrome, push it into vector
        if (checkForPalindrome(array[p])) {
            palCnt++;
            cout << array[p] << ", ";
        }
    }
    if(palCnt == 0){
        cout << " -1 ";
    }
}
int main(){
    string array[] = {"cbc", "bed", "pop", "mam", "navjivan"};
    int N = sizeof(array) / sizeof(array[0]);
    cout << "The palindrome strings from the given array are : ";
    FindAllPalindrome(array, N);       
    return 0;
}

輸出

The palindrome strings from the given array are : cbc, pop, mam,

時間複雜度 - O(N*K) 以檢查字串是否為迴文。

空間複雜度 - O(1)，因為我們沒有使用任何動態空間。

第二種方法更最佳化，因為它比第一種方法使用更少的空間。但是，兩種方法的時間複雜度相同。程式設計師還可以嘗試計算給定陣列中非迴文字串的數量以進行更多練習。