C++ 在给定的字符串数组中找到所有回文字符串

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

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

问题陈述 −我们给出了一个包含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 α) {
    // 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()函数中初始化左右变量。

步骤2.2 − 在左小于右的情况下继续遍历字符串。

步骤2.3 − 如果左右索引处的字符不同，返回false。

步骤2.4 − 将左增加1，右减少1。

步骤2.5 − 最后返回true。

步骤3 − 如果第p个索引处的字符串是回文，将‘palCnt’的值增加1，并打印字符串。

步骤4 − 最后，如果‘palCnt’的值为0，打印-1。

示例

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

bool checkForPalindrome(string α) {
    // 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) 因为我们没有使用任何动态空间。

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