Erzeugt alle möglichen Zeichenfolgen, die durch Ersetzen von Buchstaben durch die angegebenen entsprechenden Symbole gebildet werden

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
$#^

Erläuterung − Im obigen Beispiel werden insgesamt 8 Strings generiert.

Input: s = “pQ”, mp = {‘p’ : ‘#’, ‘Q’ : ‘$’}
Output:
pQ
#Q
p$
#$

Hinweise – Im obigen Beispiel werden insgesamt 4 Zeichenfolgen generiert.

Input: s = “w”, mp = {‘w’ : ‘#’}
Output:
w
#

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;
}

Ausgabe

xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^

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;
}

Ausgabe

xyZ
xy^
x#Z
x#^
$yZ
$y^
$#Z
$#^

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!