Beim Generieren aller möglichen Zeichenfolgen wird ein bestimmtes Zeichen in der Zeichenfolge durch das entsprechende Symbol ersetzt und alle möglichen Zeichenfolgen generiert. Wir erhalten eine Zeichenfolge „s“ der Größe „N“ und eine ungeordnete Karte „mp“ von Zeichenpaaren der Größe „M“. Hier können wir mp[i][0] im String „s“ durch mp[i][1] ersetzen, sodass unsere Aufgabe darin besteht, alle möglichen Strings zu generieren.
Beispiel Beispiel
Input: s = “xyZ”, mp = {‘x’ : ‘$’, ‘y’ : ‘#’, ‘Z’ : ‘^’}
Output:
xyZ
xy^
x#Z
z#^
$yZ
$y^
$#Z
$#^
Nach dem Login kopieren
Erläuterung − Im obigen Beispiel werden insgesamt 8 Strings generiert.
Input: s = “pQ”, mp = {‘p’ : ‘#’, ‘Q’ : ‘$’}
Output:
pQ
#Q
p$
#$
Nach dem Login kopieren
Hinweise – Im obigen Beispiel werden insgesamt 4 Zeichenfolgen generiert.
Input: s = “w”, mp = {‘w’ : ‘#’}
Output:
w
#
Nach dem Login kopieren
Erklärung − Im obigen Beispiel werden insgesamt 2 Strings generiert.
Methode
Bei dieser Methode verwenden wir das Konzept der rohen Gewalt, um alle möglichen Kombinationen zu finden.
Zuerst erstellen wir eine Funktion, die als Parameter eine Zeichenfolge, den aktuellen Index und die angegebene Karte akzeptiert. Der Rückgabetyp ist void.
In dieser Funktion definieren wir die Grundbedingung, dass der aktuelle Index gleich der Größe der Zeichenfolge ist, und drucken dann die Zeichenfolge aus und geben sie von der Funktion zurück.
Andernfalls haben wir zwei Möglichkeiten: Die eine besteht darin, den aktuellen Index nicht zu ändern und zum nächsten zu wechseln, was immer eine Option sein wird.
Die zweite Auswahl ist nur möglich, wenn der aktuelle Charakter einen Ersatz hat. Wenn der Ersatz vorhanden ist, rufen wir den Ersatz an.
Danach kehren wir von der Funktion zurück und sie liefert automatisch alle erforderlichen Ergebnisse.
Lassen Sie uns zum besseren Verständnis den Code der oben genannten Methode besprechen.
Beispiel
#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible strings by replacing the characters with paired symbols
void possibleStrings(string str, int idx, unordered_map<char, char> mp){
if (idx == str.size()) {
cout << str << endl;
return;
}
// Function call with the idx-th character not replaced
possibleStrings(str, idx + 1, mp);
// Replace the idx-th character
str[idx] = mp[str[idx]];
// Function call with the idx-th character replaced
possibleStrings(str, idx + 1, mp);
return;
}
int main(){
string str = "xyZ";
unordered_map<char, char> mp;
mp['x'] = '$';
mp['y'] = '#';
mp['Z'] = '^';
mp['q'] = '&';
mp['2'] = '*';
mp['1'] = '!';
mp['R'] = '@';
int idx = 0;
// Call 'possibleStrings' function to generate all possible strings
//Here in the 'possible strings' function, we have passed string 'str', index 'idx', and map 'mp'
possibleStrings(str, idx, mp);
return 0;
}
Nach dem Login kopieren
Ausgabe
xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^
Nach dem Login kopieren
Nach dem Login kopieren
Zeitliche und räumliche Komplexität
Die zeitliche Komplexität des obigen Codes beträgt O(N*2^N), da wir gerade N Elemente zurückverfolgt haben, wobei N die Größe der Zeichenfolge „s“ ist.
Die räumliche Komplexität des obigen Codes beträgt O(N*N), da wir die Zeichenfolge als vollständige Zeichenfolge senden und möglicherweise N Kopien der Zeichenfolge gleichzeitig vorhanden sind.
Backtracking-Algorithmus
Bei der vorherigen Methode hatte die von uns gesendete Zeichenfolge keinen Zeiger, was dazu führte, dass sie viel Platz beanspruchte. Um die räumliche und zeitliche Komplexität zu reduzieren, verwenden wir das Konzept des Backtracking.
Beispiel
#include <bits/stdc++.h>
using namespace std;
// Function to generate all possible strings by replacing the characters with paired symbols
void possibleStrings(string& str, int idx, unordered_map<char, char> mp){
if (idx == str.size()) {
cout << str << endl;
return;
}
// Function call with the idx-th character not replaced
possibleStrings(str, idx + 1, mp);
// storing the current element
char temp = str[idx];
// Replace the idx-th character
str[idx] = mp[str[idx]];
// Function call with the idx-th character replaced
possibleStrings(str, idx + 1, mp);
// backtracking
str[idx] = temp;
return;
}
int main(){
string str = "xyZ";
unordered_map<char, char> mp;
mp['x'] = '$';
mp['y'] = '#';
mp['Z'] = '^';
mp['q'] = '&';
mp['2'] = '*';
mp['1'] = '!';
mp['R'] = '@';
int idx = 0;
// Call 'possibleStrings' function to generate all possible strings
//Here in the 'possible strings' function, we have passed string 'str', index 'idx', and map 'mp'
possibleStrings(str, idx, mp);
return 0;
}
Nach dem Login kopieren
Ausgabe
xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^
Nach dem Login kopieren
Nach dem Login kopieren
Zeitliche und räumliche Komplexität
Die zeitliche Komplexität des obigen Codes beträgt O(N*2^N), da wir gerade N Elemente zurückverfolgt haben, wobei N die Größe der Zeichenfolge „s“ ist.
Die Speicherplatzkomplexität des obigen Codes beträgt O(N), da wir die Adresse der Zeichenfolge senden und höchstens N Stapel ausfallen.
Fazit
In diesem Tutorial haben wir ein Programm implementiert, das alle möglichen Zeichenfolgen generiert, indem es Buchstaben durch vorgegebene Symbole ersetzt. Hier haben wir die Backtracking-Methode gesehen und die zeitliche Komplexität des Codes beträgt O(N*2^N), wobei N die Größe der Zeichenfolge ist und die räumliche Komplexität mit der zeitlichen Komplexität übereinstimmt. Um die Platzkomplexität zu reduzieren, haben wir einen Backtracking-Prozess implementiert.
Das obige ist der detaillierte Inhalt vonErzeugt alle möglichen Zeichenfolgen, die durch Ersetzen von Buchstaben durch die angegebenen entsprechenden Symbole gebildet werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
