Überprüft, ob die angegebene Zeichenfolge nur in Teilsequenzen von ABC aufgeteilt werden kann

Eine Teilfolge einer Zeichenfolge ist ein Teil einer Zeichenfolge, in dem Zeichen von jeder Position (null oder mehr Elemente) der Zeichenfolge übernommen werden können, ohne die Reihenfolge der Zeichen zu ändern und eine neue Zeichenfolge zu bilden. In diesem Problem erhalten wir eine Zeichenfolge der Länge N, wobei jedes Zeichen der Zeichenfolge entweder ein „A“, „B“ oder „C“-Zeichen ist. Unsere Aufgabe besteht darin herauszufinden, dass die Zeichenfolge nur in die Teilsequenzen „ABC“ oder „Not“ aufgeteilt werden kann. Gibt „Ja“ zurück, wenn die Zeichenfolge nur in die Teilsequenz „ABC“ aufgeteilt ist, andernfalls wird „Nein“ zurückgegeben.

Input 1: str = “AABCBC” 
Output 1: yes

Anleitung – Die Aufteilungsmethode besteht darin, die Zeichenfolge wie folgt in zwei Teilsequenzen von „ABC“ aufzuteilen -

• Eine der möglichen Methoden besteht darin, die Teilfolge „ABC“ zu bilden, indem man die Zeichen mit den Indizes 0, 2 und 3 nimmt, und dann die Teilfolge „ABC“ zu bilden, indem man die Zeichen mit den Indizes 1, 4 und 5 nimmt.

• Eine andere Möglichkeit besteht darin, die Teilsequenz „ABC“ zu bilden, indem die Zeichen an den Indizes 0, 4, 5 und 1, 2, 3 abgerufen werden.

Somit kann die Zeichenfolge in zwei Teilsequenzen von „ABC“ aufgeteilt werden.

Input 2: str = “AABBBACCC”
Output 2: no

Erklärung – Für „A“, das bei Indexnummer 5 auftritt, gibt es kein „B“ danach. Daher kann die gesamte Zeichenfolge nicht in eindeutige Teilsequenzen „ABC“ aufgeteilt werden. Daher lautet die Antwort „Nein“.

Methode 1: Hashmap verwenden

Wir haben folgende zwei Beobachtungen -

• Die Größe der Zeichenfolge sollte durch 3 teilbar sein, da wir die Zeichenfolge in „ABC“ aufteilen müssen und die Anzahl der Zeichen „A“, „B“ und „C“ gleich sein sollte. Andernfalls können wir die Bedingungen nicht erfüllen.

• Wenn wir die Häufigkeiten der Zeichen „A“, „B“ und „C“ zählen, muss die Anzahl von „A“ größer oder gleich der Anzahl von „B“ und die Anzahl von „B“ sein größer oder gleich der Anzahl von „C“. Weil die Anzahl von A >= die Anzahl von B >= die Anzahl von C ist

Basierend auf den obigen Beobachtungen müssen wir drei Bedingungen überprüfen.

• sollte die Zeichenfolgengröße % 3 == 0 haben.

• sollte A-Zählung >= B-Zählung >= C-Zählung sein.

• Die letzte Bedingung sollte freq[ ‚A‘ ] == freq[ ‚B‘ ] == freq[ ‚C‘ ] sein.

Wir können eine Hash-Map verwenden, um dieses Problem zu lösen, da wir die Häufigkeit jedes Zeichens in der angegebenen Zeichenfolge „str“ speichern müssen.

Lassen Sie uns die folgende Methode Schritt für Schritt besprechen –

• Zuerst erstellen wir eine Funktion namens „checkSubsequences“, die die angegebene Zeichenfolge „str“ als Parameter verwendet und nach Möglichkeit die erforderliche Zeichenfolge „yes“ zurückgibt, andernfalls wird „no“ als Rückgabewert zurückgegeben.

• In der Funktion sind alle Schritte unten angegeben -

• Erstellen Sie die Variable „len“, um die Länge der Zeichenfolge zu speichern.

• Überprüfen Sie die erste Bedingung und geben Sie „Nein“ zurück, wenn die Länge nicht durch 3 teilbar ist.

• Erstellen Sie eine Hash-Map, um die Häufigkeiten der Zeichen „A“, „B“ und „C“ zu speichern. Daher ist die Raumkomplexität konstant.

• Verwenden Sie eine for-Schleife, um die Zeichenfolge von 0 auf weniger als len zu durchlaufen.

  • Erhöhen Sie die aktuelle Zeichenanzahl der Zeichenfolge

  • Überprüfen Sie die zweite Bedingung und geben Sie „Nein“ zurück, wenn die Anzahl von „A“ kleiner ist als die Zahl von „B“ oder die Zahl von „B“ kleiner ist als die Zahl von „C“.

• Nach der for-Schleife müssen wir die letzte dritte Bedingung überprüfen und „Nein“ zurückgeben, wenn die Anzahl von A nicht mit der Anzahl von B übereinstimmt oder die Anzahl von B nicht mit der Anzahl von C übereinstimmt.

• Wenn schließlich alle Bedingungen erfüllt sind, geben Sie „Ja“ zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// function to check subsequences of "ABC"
string checkSubsequences( string str ){
   int len = str.size(); //getting length of the string str
   // check first condition 
   if( len%3 != 0 ) {
      return "no";
   }
   map< char, int >freq; //store the count of character 'A', 'B' and 'C'
   for( int i=0; i<len; i++){
      freq[ str[i] ]++; // increase the count of the character
      //chech second condition 
      if(freq[ 'A' ] < freq[ 'B' ] || freq[ 'B' ] < freq[ 'C' ]){
         return "no";
      }
   }
   //check third condition 
   if(freq[ 'A' ] != freq[ 'B' ] || freq[ 'B' ] != freq[ 'C' ]){
      return "no";
   }
   // it is possible to split string only into subsequences of "ABC"
   return "yes";
}
// main function 
int main(){
   string str = "ABAAABCBC";// given string 
   // calling the function 'checkSubsequences' to check is it possible to split
   // string into subsequences of "ABC"
   string result = checkSubsequences( str );
   if( result == "yes" ){
      cout<< result << ", the string is splited only into the subsequences of ABC";
   }
   else {
      cout<< result << ", the string is not splited only into the subsequences of ABC.";
   }
   return 0;
}

Ausgabe

no, the string is not splited only into the subsequences of ABC.

Zeitliche und räumliche Komplexität

Die zeitliche Komplexität des obigen Codes beträgt O(N), da wir über die Zeichenfolge iterieren. wobei N die Größe der Zeichenfolge ist.

Die räumliche Komplexität des obigen Codes beträgt O(1), da wir die Häufigkeit der Zahl speichern, deren Größe konstant 3 ist.

Fazit

In diesem Tutorial haben wir ein Programm implementiert, um zu prüfen, ob eine bestimmte Zeichenfolge nur in die Teilsequenzen ABC aufgeteilt werden kann. Wir haben eine Hashing-Methode implementiert, weil wir die Häufigkeiten speichern mussten. Bei dieser Methode prüfen wir hauptsächlich drei Bedingungen. Wenn alle Bedingungen erfüllt sind, bedeutet dies, dass wir die Zeichenfolge nur in Teilsequenzen von „ABC“ aufteilen können.

Das obige ist der detaillierte Inhalt vonÜberprüft, ob die angegebene Zeichenfolge nur in Teilsequenzen von ABC aufgeteilt werden kann. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!