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.
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
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;
}
Nach dem Login kopieren
Ausgabe
Minimum number of operations required to create string B from the subsequences of the string A is: 2
Nach dem Login kopieren
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.
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;
}
Nach dem Login kopieren
Ausgabe
Minimum number of operations required to create string B from the subsequences of the string A is: 3
Nach dem Login kopieren
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!
