Menghasilkan semua rentetan yang mungkin terbentuk dengan menggantikan huruf dengan simbol sepadan yang diberikan

Menjana semua rentetan yang mungkin adalah untuk menggantikan aksara tertentu dalam rentetan dengan simbol yang sepadan dan menjana semua rentetan yang mungkin. Kami akan mendapat rentetan "s" bersaiz "N" dan peta tidak tertib "mp" pasangan aksara bersaiz "M". Di sini kita boleh menggantikan mp[i][0] dalam rentetan "s" dengan mp[i][1] supaya tugas kita ialah menjana semua rentetan yang mungkin.

Contoh Contoh

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

Penjelasan − Dalam contoh di atas, sejumlah 8 rentetan dijana.

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

Nota - Dalam contoh di atas, sejumlah 4 rentetan dijana.

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

Penjelasan − Dalam contoh di atas, sejumlah 2 rentetan dijana.

Kaedah

Dalam kaedah ini kita akan menggunakan konsep kekerasan untuk mencari semua kombinasi yang mungkin.

• Pertama, kami akan mencipta fungsi yang akan mengambil sebagai parameter rentetan, indeks semasa dan peta yang diberikan, dan jenis pemulangan akan terbatal.

• Dalam fungsi ini kita akan menentukan syarat asas bahawa indeks semasa adalah sama dengan saiz rentetan dan kemudian kita akan mencetak rentetan dan mengembalikannya daripada fungsi.

• Jika tidak, kita akan mempunyai dua pilihan, satu adalah untuk tidak menukar indeks semasa dan beralih ke yang seterusnya, yang akan sentiasa menjadi pilihan.

• Pilihan kedua hanya boleh dilakukan jika watak semasa mempunyai pengganti. Sekiranya pengganti itu wujud, maka kami akan memanggil pengganti itu.

• Selepas itu kami akan kembali dari fungsi dan ia akan secara automatik menghasilkan semua hasil yang diperlukan.

Mari kita bincangkan kod kaedah di atas untuk pemahaman yang lebih baik.

Contoh

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

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N*2^N) kerana kita baru sahaja berundur pada elemen N, dengan N ialah saiz rentetan 's'.

Kerumitan ruang kod di atas ialah O(N*N), kerana kami menghantar rentetan sebagai rentetan lengkap dan mungkin terdapat N salinan rentetan pada masa yang sama.

Algoritma penjejakan belakang

Dalam kaedah sebelum ini, rentetan yang kami hantar tidak mempunyai penunjuk, yang mengakibatkan mengambil banyak ruang. Untuk mengurangkan kerumitan ruang dan masa, kami akan menggunakan konsep backtracking.

Contoh

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

Output

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

Kerumitan masa dan ruang

Kerumitan masa kod di atas ialah O(N*2^N) kerana kita baru sahaja berundur pada elemen N, dengan N ialah saiz rentetan 's'.

Kerumitan ruang bagi kod di atas ialah O(N), kerana kami menghantar alamat rentetan dan hanya akan terdapat paling banyak N tindanan yang akan turun.

Kesimpulan

Dalam tutorial ini, kami telah melaksanakan program untuk menjana semua rentetan yang mungkin dengan menggantikan huruf dengan simbol yang diberikan. Di sini, kita telah melihat kaedah penjejakan ke belakang, dan kerumitan masa kod ialah O(N*2^N), dengan N ialah saiz rentetan dan kerumitan ruang adalah sama dengan kerumitan masa. Untuk mengurangkan kerumitan ruang, kami telah melaksanakan proses penjejakan ke belakang.

Atas ialah kandungan terperinci Menghasilkan semua rentetan yang mungkin terbentuk dengan menggantikan huruf dengan simbol sepadan yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!