Trouver la dernière chaîne palindrome dans le tableau donné

Dans ce problème, nous devons trouver la dernière chaîne palindrome du tableau. Si une chaîne est la même lors de la lecture, qu’elle soit lue depuis le début ou depuis la fin, on dit que la chaîne est un palindrome. Nous pouvons comparer les caractères de début et de fin pour vérifier si une chaîne particulière est un palindrome. Une autre façon de trouver une chaîne palindrome consiste à inverser la chaîne et à la comparer à la chaîne d'origine.

Énoncé du problème - On nous donne un tableau de longueur N contenant différentes chaînes. Nous devons trouver la dernière chaîne palindrome du tableau donné.

Exemple Exemple

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

Sortie –« tut »

Explication– La dernière chaîne palindrome du tableau donné est « tut ».

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

Sortie-"nayan"

Explication – 'nayan' est la dernière chaîne palindrome du tableau donné.

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

Sortie-""

Explication – Puisque le tableau ne contient aucune chaîne palindrome, il imprime la chaîne vide.

Méthode 1

Dans cette méthode, nous allons parcourir le tableau depuis le début et stocker la dernière chaîne palindrome dans une variable. De plus, nous comparons les caractères de début et de fin de la chaîne pour vérifier si la chaîne est un palindrome.

Algorithme

• Définissez la variable 'lastPal' pour stocker la dernière chaîne du palindrome.

• Parcourez le tableau.

• Utilisez la fonction isPalindrome() pour vérifier si la chaîne à l'index pth du tableau est un palindrome.

• Dans la fonction isPalindrome(), utilisez une boucle pour parcourir la chaîne.

• Compare les caractères str[i] et str[len - p - 1] ; si des caractères ne correspondent pas, renvoie false.

• Renvoie vrai une fois toutes les itérations de la boucle terminées.

• Si la chaîne actuelle est un palindrome, mettez à jour la valeur de la variable 'lastPal' avec la chaîne actuelle.

• Retournez "lastPal".

Exemple

#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;
}

Sortie

The last palindromic string in the given array is abba

Complexité temporelle - O(N*K) car nous parcourons le tableau et vérifions si chaque chaîne est un palindrome.

Complexité spatiale - O(1) car nous utilisons un espace constant.

Méthode 2

Dans cette méthode, nous allons parcourir le tableau en commençant par le dernier et lorsque nous trouverons la dernière chaîne palindrome, nous la renverrons. De plus, nous utilisons la méthode reverse() pour vérifier si la chaîne est un palindrome.

Algorithme

• Parcourez le tableau en commençant par le dernier.

• Utilisez la fonction isPalindrome() pour vérifier si la chaîne est un palindrome.

• Dans la fonction isPalindrome(), stockez la chaîne 'str' dans la variable 'temp'.

• Utilisez la méthode reverse() pour inverser une chaîne temporaire.

• Renvoie vrai si str et temp sont égaux. Sinon, retournez false.

• Si la chaîne au i-ième index est un palindrome, renvoyez cette chaîne.

Exemple

#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;
}

Sortie

The last palindromic string in the given array is tut

Complexité temporelle - O(N*K) puisque nous parcourons le tableau et inversons la chaîne.

Complexité spatiale - O(1) puisque nous n'utilisons pas d'espace dynamique.

Ici, nous avons appris deux méthodes pour trouver la dernière chaîne palindrome dans un tableau donné. La complexité temporelle et spatiale des deux méthodes est presque similaire, mais le deuxième code est plus lisible et meilleur que le premier.

De plus, les programmeurs peuvent essayer de trouver l'avant-dernière chaîne dans un tableau donné et s'entraîner davantage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!