Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Steps of algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024

# Generate all possible strings formed by replacing letters with given respective symbols

Harsh Goyal
0 upvote

## Introduction

This blog will discuss the approach to generate all possible strings formed by replacing letters with given respective symbols. Before jumping on the approach to generate all possible strings formed by replacing letters with given respective symbols, let’s first understand the problem,

### Problem Statement

According to the problem statement, we need to find all the characters provided in the set, and after that, we need to replace those characters with the respective symbols provided to us, and then we need to print all the possible strings.

### Sample Example

Input:

String: code

M:- { ‘c’ : ‘^’ , ‘o’ : ‘\$’ , ‘d’ : ‘#’ , ‘e’ : ‘&’ }

where M represents the symbol corresponding to each of the letter in given string i.e M[i][0] can be replaced with M[i][1],  0 ≤ i ≤ 3

Output:

• code
• cod&
• co#e
• co#&
• c\$de
• c\$d&
• c\$#e
• c\$#&
• ^ode
• ^od&
• ^o#e
• ^o#&
• ^\$de
• ^\$d&
• ^\$#&
• ^\$#e

## Approach

This approach considers replacing each character with their desired symbol and then generating all the possible strings using backtracking.

### Steps of algorithm

Step 1. Call a ‘getResult’ function, which takes three parameters, a string input, the current index of the string, and the unordered map.

Step 2. In this function, check for the base case, in which if the value of the current index and the size of the string is equal, then we need to print that string.

Step 3. If base is not triggered then, store the character at ‘lth’ index of ‘input’ string and then replace the character according to its mapping in the unordered map and then call the ‘getResult’ function by passing the next index of the current index and then after this call, replace that character at ‘lth’ index with the already stored character.

Step 4. Now call the ‘getResult’ function by passing the next index of the current index ‘l’ with the character at ‘lth’ index of string ‘input’ already replaced with the original character

## Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Function to get Result
void getResult(string input, int l, unordered_map<char, char> map)
{
// Base Case
if (l == input.size())
{
cout << input << endl;
return;
}

char temp = input[l];

// Replace the lth character
input[l] = map[input[l]];

// Call with lth character replaced
getResult(input, l + 1, map);

// Replace the lth character with its initial positon
input[l] = temp;

// Call with lth character not replaced
getResult(input, l + 1, map);

return;
}

// Driver Code
int main()
{
unordered_map<char, char> map;
map['o'] = '\$';
map['d'] = '#';
map['c'] = '^';
map['e'] = '&';

string input = "code";
// Function Call
cout << "All Possible Strings:- " << endl;
getResult(input, 0, map);

return 0;
}

Output:

All Possible Strings:-
^\$#&
^\$#e
^\$d&
^\$de
^o#&
^o#e
^od&
^ode
c\$#&
c\$#e
c\$d&
c\$de
co#&
co#e
cod&
code

### Complexity Analysis

Time Complexity: O(N * (2 ^ N))

Incall to ‘getResult()’, we are replacing all the ‘2^ N’ number of combinations where ‘N’ is the length of the string, and it takes ‘N’ time to print all the possible strings, therefore the overall time complexity is O(N * (2 ^ N)).

Space Complexity: O(1)

As we are using constant extra space, therefore the overall space complexity is O(1).

## FAQs

1. What is the time complexity to access elements from the unordered map?
The average case time complexity to access elements from the unordered map is O(1).

2. What is the difference between recursion and backtracking?
The function calls itself until it detects the base case in recursion, whereas, in backtracking, we explore all the possibilities to get the best result using recursion.

3. Can we possibly get the same result if we sort the ‘input’ string?
No, we will get the same result if we sort the ‘input’ string because we are checking all the possible permutations, but the characters specified in the map will get shuffled as the characters in the original ‘input’ string got shuffled.

## Key takeaways

In this article, we discussed to generate all possible strings formed by replacing letters with given respective symbols problem, discussed the approach to solve this problem programmatically.

Recommended Reads: Permutation of string

Check out this problem - Multiply Strings

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, all the best for your future endeavors, and Keep Coding.

Live masterclass