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  using namespace std; // Function to generate all possible strings by replacing the characters with paired symbols void possibleStrings(string str, int idx, unordered_map 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 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  using namespace std; // Function to generate all possible strings by replacing the characters with paired symbols void possibleStrings(string& str, int idx, unordered_map 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 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!