Suchen Sie die letzte Palindromzeichenfolge im angegebenen Array

In diesem Problem müssen wir die letzte Palindromzeichenfolge im Array finden. Wenn eine Zeichenfolge beim Lesen gleich ist, unabhängig davon, ob sie vom Anfang oder vom Ende gelesen wird, spricht man von einem Palindrom. Wir können die Start- und Endzeichen vergleichen, um zu überprüfen, ob eine bestimmte Zeichenfolge ein Palindrom ist. Eine andere Möglichkeit, eine Palindrom-Zeichenfolge zu finden, besteht darin, die Zeichenfolge umzukehren und mit der Originalzeichenfolge zu vergleichen.

Problemstellung – Wir erhalten ein Array der Länge N, das verschiedene Zeichenfolgen enthält. Wir müssen die letzte Palindrom-Zeichenfolge im angegebenen Array finden.

Beispiel Beispiel

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

Ausgabe –‘tut’

Erklärung– Die letzte Palindromzeichenfolge im angegebenen Array ist „tut“.

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

Ausgabe-"nayan"

Erklärung – „nayan“ ist die letzte Palindromzeichenfolge im angegebenen Array.

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

Ausgabe-""

Erklärung – Da das Array keine Palindrom-Zeichenfolge enthält, wird die leere Zeichenfolge gedruckt.

Methode 1

Bei dieser Methode durchlaufen wir das Array von Anfang an und speichern die letzte Palindromzeichenfolge in einer Variablen. Darüber hinaus vergleichen wir die Anfangs- und Endzeichen der Zeichenfolge, um zu überprüfen, ob es sich bei der Zeichenfolge um ein Palindrom handelt.

Algorithmus

• Definieren Sie die Variable „lastPal“, um die letzte Palindrom-Zeichenfolge zu speichern.

• Durchlaufen Sie das Array.

• Verwenden Sie die Funktion isPalindrome(), um zu überprüfen, ob die Zeichenfolge am p-ten Index im Array ein Palindrom ist.

• Verwenden Sie in der Funktion isPalindrome() eine Schleife, um die Zeichenfolge zu durchlaufen.

• Vergleicht str[i] und str[len - p - 1] Zeichen; gibt false zurück, wenn irgendwelche Zeichen nicht übereinstimmen.

• Gibt true zurück, nachdem alle Iterationen der Schleife abgeschlossen sind.

• Wenn die aktuelle Zeichenfolge ein Palindrom ist, aktualisieren Sie den Wert der Variablen „lastPal“ mit der aktuellen Zeichenfolge.

• Geben Sie „lastPal“ zurück.

Beispiel

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

Ausgabe

The last palindromic string in the given array is abba

Zeitkomplexität – O(N*K), weil wir das Array durchlaufen und prüfen, ob jede Zeichenfolge ein Palindrom ist.

Raumkomplexität – O(1), weil wir konstanten Raum verwenden.

Methode 2

Bei dieser Methode durchlaufen wir das Array, beginnend mit dem letzten, und wenn wir die letzte Palindrom-Zeichenfolge finden, geben wir sie zurück. Zusätzlich verwenden wir die Methode reverse(), um zu prüfen, ob es sich bei der Zeichenfolge um ein Palindrom handelt.

Algorithmus

• Durchlaufen Sie das Array, beginnend mit dem letzten.

• Verwenden Sie die Funktion isPalindrome(), um zu überprüfen, ob die Zeichenfolge ein Palindrom ist.

• Speichern Sie in der Funktion isPalindrome() die Zeichenfolge „str“ in der Variablen „temp“.

• Verwenden Sie die Methode reverse(), um eine temporäre Zeichenfolge umzukehren.

• Gibt true zurück, wenn str und temp gleich sind. Andernfalls wird false zurückgegeben.

• Wenn die Zeichenfolge am i-ten Index ein Palindrom ist, geben Sie diese Zeichenfolge zurück.

Beispiel

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

Ausgabe

The last palindromic string in the given array is tut

Zeitliche Komplexität – O(N*K), da wir das Array durchlaufen und die Zeichenfolge umkehren.

Raumkomplexität – O(1), da wir keinen dynamischen Raum verwenden.

Hier haben wir zwei Methoden kennengelernt, um die letzte Palindrom-Zeichenfolge in einem bestimmten Array zu finden. Die zeitliche und räumliche Komplexität beider Methoden ist nahezu ähnlich, der zweite Code ist jedoch besser lesbar und besser als der erste.

Außerdem können Programmierer versuchen, die vorletzte Zeichenfolge in einem bestimmten Array zu finden und mehr üben.

Das obige ist der detaillierte Inhalt vonSuchen Sie die letzte Palindromzeichenfolge im angegebenen Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!