Prüft, ob ein String in drei Teilstrings aufgeteilt werden kann, wobei ein Teilstring ein Teilstring der anderen beiden Teilstrings ist

In diesem Problem müssen wir die gegebene Zeichenfolge so aufteilen, dass die dritte Teilzeichenfolge eine Teilzeichenfolge der ersten beiden Teilzeichenfolgen sein kann.

Überlegen wir uns eine Lösung. Die dritte Zeichenfolge kann nur dann eine Teilzeichenfolge der ersten beiden Zeichenfolgen sein, wenn die ersten beiden Zeichenfolgen alle Zeichen der dritten Zeichenfolge enthalten. Wir müssen also mindestens ein Zeichen mit einer Häufigkeit von mehr als 3 in der angegebenen Zeichenfolge finden und können die dritte Teilzeichenfolge dieses einzelnen Zeichens verwenden.

Problemstellung – Wir erhalten eine Zeichenfolge str mit N Kleinbuchstaben. Wir müssen prüfen, ob wir die Zeichenfolge in drei Teilzeichenfolgen a, b und c aufteilen können, sodass Teilzeichenfolge c eine Teilzeichenfolge von a und b ist. Geben Sie „Ja“ oder „Nein“ aus, je nachdem, ob 3 Teilzeichenfolgen gefunden werden können.

Beispiel

Input –  str = "tutorialsPoint"

Output – ‘Yes’

Anleitung

Hier können wir die Zeichenfolge in „tu“, „torialsPoin“ und „t“ aufteilen. Daher ist die dritte Zeichenfolge eine Teilzeichenfolge der ersten beiden Zeichenfolgen.

Input –  str = "tutorials"

Output – ‘No’

Anleitung

Wir können die Zeichenfolge basierend auf der gegebenen Bedingung nicht in drei Teilzeichenfolgen aufteilen, da die Häufigkeit eines Zeichens nicht größer als 3 ist.

Input –  str = "hhhhhhhh"

Output – ‘Yes’

Anleitung

Gemäß den gegebenen Bedingungen können die drei Teilzeichenfolgen „h“, „h“ und „hhhhhh“ sein.

Methode 1

Bei dieser Methode verwenden wir ein Array, um die Häufigkeit jedes Zeichens zu speichern. Danach prüfen wir, ob Zeichen mit einer Häufigkeit größer oder gleich 3 vorliegen.

Algorithmus

• Schritt 1 – Definieren Sie das „freq“-Array mit einer Länge von 26.

• Schritt 2 – Durchlaufen Sie die Zeichenfolge, um die Häufigkeit der Zeichen zu zählen. Erhöhen Sie in der for-Schleife den Wert von freq[str[i] – „a“]. Hier ergibt str[i] – „a“ einen Index zwischen 0 und 26.

• Schritt 3 – Durchlaufen Sie nun das Array „freq“ und geben Sie „true“ zurück, wenn der Wert an einem Array-Index größer als „3“ ist.

• Schritt 4 – Geben Sie true zurück, wenn die Schleife endet.

• Schritt 5 – Geben Sie „Ja“ oder „Nein“ basierend auf dem Rückgabewert der Funktion isSUbStringPossible() aus.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   // array to store the frequency
   int freq[26] = {0};
   
   // Iterate over the string
   for (int i = 0; i < len; i++){
   
      // count the frequency of each character
      freq[str[i] - 'a']++;
   }
   
   // Traverse the frequency array
   for (int i = 0; i < 26; i++){
   
      // If the frequency of any character is greater than or equal to 3, then return "Yes."
      if (freq[i] >= 3){
         return "Yes";
      }
   }
   
   // Otherwise
   return "No";
}
int main(){
   string str = "tutorialsPoint";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Ausgabe

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Zeitkomplexität – O(N), wenn wir über die Zeichenfolge iterieren.

Raumkomplexität – O(1), da wir Arrays mit konstanter Länge verwenden.

Methode 2

Bei dieser Methode konvertieren wir zunächst die Zeichenfolge in ein Zeichenarray. Danach verwenden wir die Methode count(), um die Häufigkeit bestimmter Zeichen im Array zu zählen.

Algorithmus

• Schritt 1 – Erstellen Sie ein Array der Größe „len + 1“, wobei „len“ die Stringlänge ist.

• Schritt 2 – Kopieren Sie die Zeichenfolge mit der Methode strcpy() in ein char-Array.

• Schritt 3 – Verwenden Sie eine for-Schleife für insgesamt 26 Iterationen.

• Schritt 4 – Verwenden Sie in der for-Schleife die Methode count(), um die Anzahl der Vorkommen eines bestimmten Zeichens zu zählen.

Die Methode

count() akzeptiert als erstes Argument einen Verweis auf die Startposition, als zweites Argument einen Verweis auf die Endposition und als drittes Argument ein Zeichen.

Hier müssen wir den ASCII-Wert des Zeichens als Parameter übergeben und verwenden I + „a“, um den Wert zu erhalten.

• Schritt 5 – Geben Sie „true“ zurück, wenn die count()-Methode größer oder gleich 3 zurückgibt.

• Schritt 6 – Geben Sie false zurück, wenn die Schleife endet.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to Check if a string can be split into 3 substrings such that one of them is a substring of the other two
string isSubStringPossible(string str, int len){

   //    converting str to char array.
   char char_array[len + 1];
   
   // copy string to char array
   strcpy(char_array, str.c_str());
   
   // make 26 iterations
   for (int i = 0; i < 26; i++){
   
      // Using count() to count the occurrence of each character in the array, and return 'yes' if any character occurs more than 2 times.
      if (count(char_array, char_array + len, i + 'a') >= 2)
         return "YES";
   }
   return "NO";
}
int main(){
   string str = "tutorials";
   int len = str.length();
   cout << "The given string can be splited into 3 substrings such that one of them is a substring of the other two - " << isSubStringPossible(str, len);
   return 0;
}

Ausgabe

The given string can be splited into 3 substrings such that one of them is a substring of the other two - Yes

Zeitliche Komplexität – O(N), da die count()-Methode über das char-Array iteriert, um die Anzahl der Zeichen zu zählen. Außerdem benötigt die Methode strcpy() O(N) Zeit.

Raumkomplexität – O(N), weil wir die Zeichenfolge in einem Zeichenarray speichern.

Fazit

Wir haben zwei Möglichkeiten kennengelernt, einen String in drei Teilstrings aufzuteilen, sodass ein Teilstring ein Teilstring von zwei anderen Teilstrings sein kann. Der Code der zweiten Methode ist besser lesbar und anfängerfreundlicher, aber zeit- und platzaufwändiger.

Das obige ist der detaillierte Inhalt vonPrüft, ob ein String in drei Teilstrings aufgeteilt werden kann, wobei ein Teilstring ein Teilstring der anderen beiden Teilstrings ist. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!