Generates all possible strings formed by replacing letters with the given corresponding symbols

Generating all possible strings is to replace a certain character in the string with the corresponding symbol and generate all possible strings. We will get a string "s" of size "N" and an unordered map "mp" of character pairs of size "M". Here we can replace mp[i][0] in string "s" with mp[i][1] so that our task is to generate all possible strings.

ExampleExample

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

Explanation − In the above example, a total of 8 strings are generated.

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

Description - In the above example, a total of 4 strings are generated.

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

Explanation − In the above example, a total of 2 strings are generated.

method

In this approach we will use the concept of brute force to find all possible combinations.

• First, we will create a function that will take as parameters a string, the current index, and the given map, and the return type will be void.

• In this function, we will define the basic condition that the current index is equal to the size of the string, and then we will print the string and return it from the function.

• Otherwise, we will have two options, one is to not change the current index and move to the next one, which will always be an option.

• The second option is only possible if the current character has a replacement. If the replacement exists, then we will call the replacement.

• Afterwards we will return from the function, which will automatically produce all the required results.

Let us discuss the code of the above method for better understanding.

Example

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

Time and space complexity

The time complexity of the above code is O(N*2^N) because we have just backtracked on N elements, where N is the size of the string 's'.

The space complexity of the above code is O(N*N), because we send the string as a complete string, and there may be N copies of the string at the same time.

Backtracking algorithm

In the previous method, the string we sent did not have a pointer, which took up a lot of space. To reduce space and time complexity, we will use the concept of backtracking.

Example

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

Time and space complexity

The time complexity of the above code is O(N*2^N) because we have just backtracked on N elements, where N is the size of the string 's'.

The space complexity of the above code is O(N), because we are sending the address of the string, and there will only be at most N stacks going down.

in conclusion

In this tutorial, we have implemented a program to generate all possible strings by replacing letters with given symbols. Here, we have seen the backtracking method, and the time complexity of the code is O(N*2^N), where N is the size of the string, and the space complexity is the same as the time complexity. To reduce space complexity, we have implemented a backtracking process.

The above is the detailed content of Generates all possible strings formed by replacing letters with the given corresponding symbols. For more information, please follow other related articles on the PHP Chinese website!