C++ 在给定的数组中找到最后一个回文字符串

在这个问题中，我们需要找到数组中的最后一个回文字符串。如果任何字符串从头部或尾部开始阅读时都是相同的，我们可以说这个字符串是回文的。我们可以比较起始和末尾的字符来检查特定字符串是否是回文的。另一种找到回文字符串的方法是将字符串反转并与原始字符串进行比较。

问题陈述 - 我们已经给定了一个长度为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++) {
      // compare first ith and last ith character
      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])) {
          // if the current string is palindrome, then update the lastPal string
          lastPal = arr[p];
      }
   }
   return lastPal;
}
int main() {
   string arr[] = {"werwr", "rwe", "nayan", "abba", "rte"};
   int N = sizeof(arr)/sizeof(arr[0]);
   cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
   return 0;
}

输出

The last palindromic string in the given array is 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 a default value if no palindrome is found
    return "No palindromic string found";
}

int main() {
    string arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "The last palindromic string in the given array is " << LastPalindrome(arr, N);
    return 0;
}

输出

The last palindromic string in the given array is tut

时间复杂度 – O（N * K），因为我们遍历数组并翻转字符串。

空间复杂度 – O（1），因为我们不使用动态空间。

在这里，我们学到了两种方法来找到给定数组中的最后一个回文字符串。这两种方法的时间和空间复杂度几乎相似，但第二个代码更可读，比第一个更好。

此外，程序员可以尝试找到给定数组中的倒数第二个字符串，并进行更多的练习。