在给定的字符串数组中查找所有回文字符串
我们需要在这个问题中从给定的数组中查找所有回文字符串。如果我们能从开头和结尾读出相同的字符串，则该字符串为回文字符串。
我们可以使用两种方法来检查字符串是否为回文字符串。在第一种方法中，我们反转字符串并将其与原始字符串进行比较；在第二种方法中，我们不断从头到尾比较字符串字符。
问题陈述− 我们给出了一个包含 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 − 定义"回文"列表来存储所有回文字符串。
步骤 2 − 遍历数组。
步骤 3 − 执行 checkForPalindrome() 函数来检查第 p 个索引处的字符串是否为回文。
步骤 3.1 − 将字符串存储到函数中的"temp"字符串中。
步骤 3.2 − 使用 reverse() 方法反转 alpha 字符串。
步骤 3.3 − 比较 temp 和 alpha 后返回布尔值。
步骤 4 − 如果特定字符串是回文，则将其推送到"回文"列表。
步骤 5 − 返回回文列表。
示例
#include <bits/stdc++.h>
using namespace std;
bool checkForPalindrome(string &alpha) {
// 复制字符串
string temp = alpha;
// 反转字符串
reverse(alpha.begin(), alpha.end());
// 如果字符串及其反转相等，则返回 true。否则返回 false。
return temp == alpha;
}
vector<string> FindAllPalindrome(string array[], int N) {
vector<string> palindromes;
// 遍历数组
for (int p = 0; p < N; p++) {
// 如果字符串是回文，则将其推送到 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]);
// 打印所需答案
vector<string> list = FindAllPalindrome(array, N);
if (list.size() == 0)
cout << "-1";
else {
cout << "给定数组中的回文字符串为 : ";
for (string str : list) {
cout << str << ", ";
}
}
return 0;
}
输出
给定数组中的回文字符串为：tut、nanan、
时间复杂度− O(N*K)，其中 N 是数组长度，K 是字符串的最大长度。
空间复杂度− O(N + K)，因为我们将原始字符串存储到"临时"字符串中，并将回文字符串存储在列表中。
方法 2
在这种方法中，我们直接打印回文字符串，而不是将它们存储在列表中。此外，我们从头到尾匹配字符串的字符来检查字符串是否为回文，而不是使用 reverse() 方法。
算法
步骤 1 - 用 0 初始化"palCnt"变量，以将回文字符串的数量存储在数组中。
步骤 2 - 遍历字符串并通过将字符串作为参数传递来执行 checkForPalindrome() 函数以检查字符串是否为回文。
步骤 2.1 - 初始化 checkForPalindrome() 函数中的 left 和 right 变量。
步骤 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 &alpha) {
// 初始化开始和结束索引
int left = 0;
int right = alpha.length() - 1;
// 遍历字符串
while (left < right) {
// 比较从开始和结束的字符
if (alpha[left] != alpha[right]) {
return false;
}
// 更改指针的值
left++;
right--;
}
return true;
}
void FindAllPalindrome(string array[], int N) {
int palCnt = 0;
//遍历数组
for (int p = 0; p < N; p++) {
// 如果字符串是回文，则将其推入向量
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 << "给定数组中的回文字符串为：";
FindAllPalindrome(array, N);
return 0;
}
输出
给定数组中的回文字符串为：cbc、pop、mam、
时间复杂度− O(N*K) 来检查字符串是否为回文。
空间复杂度− O(1)，因为我们不使用任何动态空间。
第二种方法更优化，因为它使用的空间比第一种方法更少。但是，两种方法的时间复杂度相同。程序员还可以尝试计算给定数组中的非回文字符串，以进行更多练习。
