在给定数组中查找最后一个回文字符串

---

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

问题陈述 – 我们给定了一个长度为 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)，因为我们没有使用动态空间。

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

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