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

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

问题陈述 - 我们给定一个长度为N的数组，其中包含不同的字符串。我们需要找到给定数组中的最后一个回文字符串。

示例例子

输入– arr[] = {"werwr", "rwe", "nayan", "tut", "rte"};

输出 – ‘tut’

Explanation– 给定数组中的最后一个回文字符串是‘tut’。

输入– arr[] = {"werwr", "rwe", "nayan", "acd", "sdr"};

输出-“nayan”

Explanation – ‘nayan’是给定数组中的最后一个回文字符串。

输入– arr[] = {"werwr", "rwe", "jh", "er", "rte"};

输出-“”

说明 – 由于数组不包含任何回文字符串，因此它会打印空字符串。

方法 1

在这种方法中，我们将从头开始遍历数组并将最后一个回文字符串存储在变量中。另外，我们还会比较字符串的开头和结尾字符，以检查字符串是否是回文。

算法

• 定义变量‘lastPal’来存储最后一个回文字符串。

• 遍历数组。

• 使用isPalindrome()函数来检查数组中第pth索引处的字符串是否是回文。

• 在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()方法反转临时字符串。

• 如果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)，因为我们不使用动态空间。

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

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

以上是在给定的数组中找到最后一个回文字符串的详细内容。更多信息请关注PHP中文网其他相关文章！