在给定数组中查找最后一个回文字符串
在这个问题中，我们需要在数组中找到最后一个回文字符串。如果任何字符串在读取时相同，无论是从开头还是结尾开始读取，我们都可以说该字符串是回文。我们可以比较起始和结束字符来检查特定字符串是否是回文。查找回文字符串的另一种方法是反转字符串并将其与原始字符串进行比较。
问题陈述– 我们给出了一个长度为 N 的数组，其中包含不同的字符串。我们需要在给定的数组中找到最后一个回文字符串。
示例
输入– arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};
输出– 'tut'
解释– 'tut' 是给定数组中的最后一个回文字符串。
输入– arr[] = {"werwr", "rwe", "nayan", "acd", "sdr"};
输出– 'nayan'
解释– 'nayan' 是给定数组中的最后一个回文字符串。
输入– arr[] = {"werwr", "rwe", "jh", "er", "rte"};
输出– ""
解释– 由于数组不包含任何回文字符串，因此它会打印空字符串。
方法 1
在此方法中，我们将从头开始遍历数组，并将最后一个回文字符串存储在变量中。另外，我们将从头到尾比较字符串字符，以检查字符串是否为回文。
算法
定义"lastPal"变量来存储最后一个回文字符串。
遍历数组。
使用 isPalindrome() 函数检查数组中第 p 个索引处的字符串是否为回文。
在 isPalindrome() 函数中，使用循环遍历字符串。
比较 str[i] 和 str[len - p - 1] 字符；如果任何字符不匹配，则返回 false。
循环的所有迭代完成后返回 true。
如果当前字符串是回文，则使用当前字符串更新"lastPal"变量的值。
返回"lastPal"。
示例
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string &str) {
int size = str.length();
for (int p = 0; p < size / 2; p++) {
// 比较第一个和最后一个字符
if (str[p] != str[size - p - 1]) {
return false;
}
}
return true;
}
string LastPalindrome(string arr[], int N) {
string lastPal = "";
for (int p = 0; p < N; p++) {
if (isPalindrome(arr[p])) {
// 如果当前字符串是回文，则更新 lastPal 字符串
lastPal = arr[p];
}
}
return lastPal;
}
int main() {
string arr[] = {"werwr", "rwe", "nayan", "abba", "rte"};
int N = sizeof(arr)/sizeof(arr[0]);
cout << "给定数组中的最后一个回文字符串是 " << LastPalindrome(arr, N);
return 0;
}
输出
给定数组中的最后一个回文字符串是 abba
时间复杂度 – O(N*K)，因为我们遍历数组并检查每个字符串是否为回文。
空间复杂度 – O(1)，因为我们使用常数空间。
方法 2
在这种方法中，我们将从最后一个开始遍历数组，当我们从最后一个找到第一个回文字符串时，我们将返回它。另外，我们使用 reverse() 方法来检查字符串是否为回文。
算法
从最后一个开始遍历数组。
使用 isPalindrome() 函数检查字符串是否为回文。
在 isPalindrome() 函数中，将"str"字符串存储在"temp"变量中。
使用 reverse() 方法反转 temp 字符串。
如果 str 和 temp 相等，则返回 true。否则，返回 false。
如果第 i 个索引处的字符串是回文，则返回该字符串。
示例
#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string &str) {
string temp = str;
reverse(temp.begin(), temp.end());
return str == temp;
}
string LastPalindrome(string array[], int N) {
for (int p = N - 1; p >= 0; p--) {
if (isPalindrome(array[p])) {
return array[p];
}
}
// 如果未找到回文，则返回默认值
return "No palindromic string found";
}
int main() {
string arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};
int N = sizeof(arr) / sizeof(arr[0]);
cout << "给定数组中的最后一个回文字符串是 " << LastPalindrome(arr, N);
return 0;
}
输出
给定数组中的最后一个回文字符串是 tut
时间复杂度 – O(N*K)，因为我们遍历数组并反转字符串。
空间复杂度 – O(1)，因为我们不使用动态空间。
在这里，我们学习了两种在给定数组中查找最后一个回文字符串的方法。两种方法的时间和空间复杂度几乎相同，但第二种代码比第一种更具可读性且更好。
此外，程序员可以尝试在给定的数组中找到倒数第二个字符串并进行更多练习。
