Génère toutes les chaînes possibles formées en remplaçant les lettres par les symboles correspondants donnés

Générer toutes les chaînes possibles consiste à remplacer un certain caractère dans la chaîne par le symbole correspondant et à générer toutes les chaînes possibles. Nous obtiendrons une chaîne "s" de taille "N" et une carte non ordonnée "mp" de paires de caractères de taille "M". Ici, nous pouvons remplacer mp[i][0] dans la chaîne "s" par mp[i][1] afin que notre tâche soit de générer toutes les chaînes possibles.

Exemple Exemple

Input: s = “xyZ”, mp = {‘x’ : ‘$’, ‘y’ : ‘#’, ‘Z’ : ‘^’}
Output: 
xyZ
xy^
x#Z
z#^
$yZ
$y^
$#Z
$#^

Explication - Dans l'exemple ci-dessus, un total de 8 chaînes sont générées.

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

Notes - Dans l'exemple ci-dessus, un total de 4 chaînes sont générées.

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

Explication - Dans l'exemple ci-dessus, un total de 2 chaînes sont générées.

Méthode

Dans cette méthode nous utiliserons la notion de force brute pour trouver toutes les combinaisons possibles.

• Tout d'abord, nous allons créer une fonction qui prendra comme paramètres une chaîne, l'index actuel et la carte donnée, et le type de retour sera nul.

• Dans cette fonction, nous définirons la condition de base selon laquelle l'index actuel est égal à la taille de la chaîne, puis nous imprimerons la chaîne et la renverrons de la fonction.

• Sinon, nous aurons deux options, l'une est de ne pas changer l'index actuel et de passer au suivant, ce qui sera toujours une option.

• La deuxième sélection n'est possible que si le personnage actuel a un remplaçant. Si le remplacement existe, nous appellerons le remplacement.

• Ensuite, nous reviendrons de la fonction et elle produira automatiquement tous les résultats requis.

Discutons du code de la méthode ci-dessus pour une meilleure compréhension.

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*2^N) car nous venons de revenir en arrière sur N éléments, où N est la taille de la chaîne 's'.

La complexité spatiale du code ci-dessus est O(N*N), car nous envoyons la chaîne sous forme de chaîne complète et il peut y avoir N copies de la chaîne en même temps.

Algorithme de retour en arrière

Dans la méthode précédente, la chaîne que nous envoyions n'avait pas de pointeur, ce qui prenait beaucoup de place. Pour réduire la complexité spatiale et temporelle, nous utiliserons le concept de backtracking.

Exemple

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

Sortie

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

Complexité temporelle et spatiale

La complexité temporelle du code ci-dessus est O(N*2^N) car nous venons de revenir en arrière sur N éléments, où N est la taille de la chaîne 's'.

La complexité spatiale du code ci-dessus est O(N), car nous envoyons l'adresse de la chaîne, et il n'y aura au plus N piles qui descendront.

Conclusion

Dans ce tutoriel, nous avons implémenté un programme pour générer toutes les chaînes possibles en remplaçant les lettres par des symboles donnés. Ici, nous avons vu la méthode de retour en arrière, et la complexité temporelle du code est O(N*2^N), où N est la taille de la chaîne, et la complexité spatiale est la même que la complexité temporelle. Pour réduire la complexité de l'espace, nous avons mis en place un processus de retour en arrière.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!