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).

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.

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.

Table of contents

Introduction

1.1.

Problem Statement

1.2.

Sample Example

Approach

2.1.

Steps of algorithm

Implementation in C++

3.1.

Complexity Analysis

FAQs

Key takeaways

Last Updated: Mar 27, 2024

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

Author Harsh Goyal

Do you think IIT Guwahati certified course can help you in your career?

Yes

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

You can also try this code with Online C++ Compiler

Run Code

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

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).
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.
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.