Fügen Sie die minimale Teilsequenz hinzu, die zum Anhängen von Zeichenfolge A erforderlich ist, um Zeichenfolge B zu erhalten

In diesem Problem müssen wir str2 unter Verwendung der Teilfolge von str1 konstruieren. Um dieses Problem zu lösen, können wir die Teilsequenz von str1 so finden, dass sie die Teilzeichenfolge mit der maximalen Länge von str2 abdeckt. Hier lernen wir zwei verschiedene Möglichkeiten kennen, das Problem zu lösen.

Problemstellung– Wir erhalten zwei Zeichenfolgen unterschiedlicher Länge: str1 und str2. Wir müssen str2 aus str1 gemäß den folgenden Bedingungen konstruieren.

• Wählen Sie eine beliebige Teilsequenz aus str1 aus und hängen Sie sie an eine neue Zeichenfolge an (zunächst leer).

Wir müssen die Mindestanzahl an Operanden zurückgeben, die zum Erstellen von str2 erforderlich sind, oder -1 ausgeben, wenn str2 nicht erstellt werden kann.

Beispiel

Geben Sie ein – str1 = „acd“, str2 = „adc“

Ausgabe– 2

Anleitung

Die erste Teilsequenz in

• str1 ist „ad“. Unsere Zeichenfolge könnte also „ad“ lauten.

• Danach können wir die Teilsequenz „c“ von str1 abrufen und an „ad“ anhängen, um sie zu „adc“ zu machen.

Eingabe– str1 = „adcb“, str2 = „abdca“

Ausgabe–3

Anleitung

• Die erste Teilsequenz ist „ab“ in str1.

• Danach können wir die Zeichenfolge „dc“ erhalten und die resultierende Zeichenfolge ist „abdc“

• Als nächstes können wir die Teilsequenz „a“ verwenden, um die endgültige Zeichenfolge „abdca“ zu generieren.

Methode 1

In dieser Methode iterieren wir über str1, um mehrere Teilsequenzen zu finden und sie an die resultierende Zeichenfolge anzuhängen.

Algorithmus

• Definieren Sie das Array „arr“ mit der Länge 26 und initialisieren Sie alle Elemente auf 0, um das Vorhandensein von Zeichen in str1 zu speichern.

• Iterieren Sie str1 und aktualisieren Sie den Wert des Array-Elements entsprechend dem ASCII-Wert des Zeichens

• Definieren Sie die Variable „last“ und initialisieren Sie sie mit -1, um den Überblick über das zuletzt besuchte Element zu behalten. Definieren Sie außerdem die Variable „cnt“ und initialisieren Sie sie auf 0, um die Anzahl der Vorgänge zu speichern.

• Beginnen Sie mit einer Schleife, um str2 zu durchlaufen.

• Wenn sich das aktuelle Zeichen nicht in str1 befindet, geben Sie -1 zurück.

• Initialisieren Sie die Variable „j“ mit dem Wert „last + 1“.

• Verwenden Sie eine While-Schleife, um zu iterieren, bis der Wert von j kleiner als len ist und str1[j] nicht gleich dem Zeichen

ist

• Wenn der Wert von „j“ größer als „len“ ist, iterieren wir über „str1“. Erhöhen Sie den Wert der Variablen „cnt“, initialisieren Sie „last“ auf -1, da wir erneut über „str1“ iterieren müssen, verringern Sie den Wert von „I“ um 1, da wir das aktuelle Zeichen erneut berücksichtigen müssen, und verwenden Sie weiterhin Schlüsselwort „continue“ Iterieren.

• Aktualisieren Sie den Wert der „letzten“ Variablen auf „j“.

• Gib „cnt + 1“ zurück, nachdem alle Iterationen der Schleife abgeschlossen sind. Hier müssen wir „1“ zu „cnt“ hinzufügen, da wir die letzte Operation nicht berücksichtigen.

Beispiel

#include <iostream>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   int len = str1.length();
   // creating an array of size 26 to store the presence of characters in string str1.
   int arr[26] = {0};
   // storing the presence of characters in string str1.
   for (int i = 0; i < len; i++){
      arr[str1[i] - 'a']++;
   }
   // store the last iterated index of string str1.
   int last = -1;
   //  to store the count of operations.
   int cnt = 0;
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // if the character is not present in string str1, then return -1.
      if (arr[ch - 'a'] == 0){
         return -1;
      }
      // start iterating from the jth index of string str1 to find the character ch.
      int j = last + 1;
      while (j < len && str1[j] != ch){
          j++;
      }
      // if j is equal to the length of string str1, then increment the count, set last to -1, and decrement i.
      if (j >= len){
         cnt++;
         last = -1;
         --i;
         continue;
      }
      // set last to j.
      last = j;
   }
   // return cnt + 1 as we haven't counted the last operation.
   return cnt + 1;
}
int main(){
   string str1 = "acd", str2 = "adc";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Ausgabe

Minimum number of operations required to create string B from the subsequences of the string A is: 2

Zeitkomplexität – O(N*M), wobei N die Länge von str2 und M die Länge von str1 ist.

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

Methode 2

Bei dieser Methode verwenden wir Zuordnungs- und Erfassungsdatenstrukturen, um die Effizienz der oben genannten Methode zu verbessern. Die Logik zur Lösung des Problems ist dieselbe wie oben.

Algorithmus

• Definieren Sie „chars_mp“, um char -> sets{} als Schlüssel-Wert-Paare zu speichern.

• Speichern Sie in der Karte den Satz von Indizes, in denen bestimmte Zeichen in der Zeichenfolge str1 vorhanden sind

• Definieren Sie die Variablen „last“ und „cnt“

• Beginnen Sie mit dem Durchlaufen von Str2. Wenn die Größe der Sammlung, die den aktuellen Zeichenindex enthält, Null ist, wird -1 zurückgegeben.

• Finden Sie die Obergrenze von „letzter“ im aktuellen Zeichenindexsatz.

• Wenn die Obergrenze nicht gefunden wird, erhöhen Sie den Wert von „cnt“ um 1, setzen Sie „last“ auf -1, verringern Sie den Wert von „I“ um 1 und verwenden Sie das Schlüsselwort continue. p>

• Aktualisieren Sie den Wert der „letzten“ Variablen.

• Nachdem die Schleifeniteration abgeschlossen ist, geben Sie den Wert der Variable „cnt“ zurück

Beispiel

#include <iostream>
#include <map> 
#include <set>
using namespace std;

// function to count the minimum number of operations required to get string str2 from subsequences of string str1.
int minOperations(string str1, string str2){
   // Length of string str1
   int len = str1.length();
   // creating the map to store the set of indices for each character in str1
   map<char, set<int>> chars_mp;
   // Iterate over the characters of str1 and store the indices of each character in the map
   for (int i = 0; i < len; i++){
      chars_mp[str1[i]].insert(i);
   }
   // store the last visited index of str1
   int last = -1;
   // Stores the required count
   int cnt = 1;
   // Iterate over the characters of str2
   for (int i = 0; i < str2.length(); i++){
      char ch = str2[i];
      // If the set of indices of str2[i] is empty, then return -1
      if (chars_mp[ch].size() == 0){
         return -1;
      }
      // If the set of indices of str2[i] is not empty, then find the upper bound of last in the set of indices of str2[i]
      // It finds the smallest index of str2[i] which is greater than last
      auto it = chars_mp[ch].upper_bound(last);
      // If the upper bound is equal to the end of the set, then increment the count and update last to -1
       if (it == chars_mp[ch].end()){
          last = -1;
          cnt++;
          // Decrement I by 1 to process the current character again
          --i;
          continue;
      }
      // Update last to the current index
      last = *it;
   }
   return cnt;
}
int main(){
   string str1 = "adcb", str2 = "abdca";
   int operations = minOperations(str1, str2);
   cout << "Minimum number of operations required to create string B from the subsequences of the string A is: " << operations << "\n";
   return 0;
}

Ausgabe

Minimum number of operations required to create string B from the subsequences of the string A is: 3

Zeitkomplexität – O(N*logN), da wir über str2 iterieren und die Obergrenze des „letzten“ Index in der Schleife finden.

Raumkomplexität – O(N), weil wir eine Karte zum Speichern von Zeichenindizes verwenden.

Das obige ist der detaillierte Inhalt vonFügen Sie die minimale Teilsequenz hinzu, die zum Anhängen von Zeichenfolge A erforderlich ist, um Zeichenfolge B zu erhalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!