在给定的字符串数组中查找所有回文字符串

---

在这个问题中，我们需要从给定的数组中找到所有回文字符串。如果一个字符串从开头到结尾读取都相同，则称该字符串为回文。

我们可以使用两种方法来检查字符串是否为回文。在第一种方法中，我们反转字符串并将其与原始字符串进行比较，在第二种方法中，我们不断比较字符串的字符从开头到结尾。

问题陈述 - 我们给定一个包含 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)，因为我们没有使用任何动态空间。

第二种方法更优化，因为它比第一种方法使用更少的空间。但是，两种方法的时间复杂度相同。程序员还可以尝试计算给定数组中非回文字符串的数量以进行更多练习。