In this article, we will learn to generate strings from codes. This problem involves the concept of mapping as well as recursion. It is a perfect practice problem to help you master recursion. As we all know that recursion is a slightly tricky concept to master. Let’s move towards the problem statement.

## Problem Statement

*Given a mapping of strings with numbers. The mapping is such that the alphabets are mapped with numbers in the following manner.*

*A – 1**B – 2**C – 3**… …**… …**Z – 26*

*You are also given a number in the form of a character array. You have to generate all possible strings that you can generate from this numerical code.*

Let’s consider the following examples

```
Example 1:
Code: 1234
String_1: (1)(2)(3)(4) = ABCD
String_2: (12)(3)(4) = LCD
String_3: (1)(23)(4) = AWD
Please note that the combination: (34) is not valid because the given mapping is only upto 26
Example 2:
Code: 1212
String_1: (1)(2)(1)(2) = ABAB
String_2: (12)(1)(2) = LAB
String_3: (1)(21)(2) = AUB
String_4: (1)(2)(12) = ABL
String_5: (12)(12) = LL
```

## Concept

We will construct the algorithm in the following manner

- We will maintain two arrays
- One for the input
- And the other for the output

- We will iterate over the input string using a variable
*i*- The variable
*i*will denote the index we are currently at - At every index except the last index, we have two options
- Either we can consider this digit as a number
- If we consider single number as a digit, we can make a recursive call on the function as
- generate_string(remaining array)
- And we will keep on repeating the same process, until we hit the base case

- Or we can group this digit with the next digit to form a number
- Grouping is possible only if the grouped number is less than 27
- Similar to the earlier case, we will now make a recursive call on the remaining string.

- Either we can consider this digit as a number

- The variable
- The base case for this problem will be reaching the last index of the input string

### Algorithm

```
void generate_strings(char *input, char *output, int i, int j)
{
// base case
// if we've reached the to NULL character of the input string
if(input[i] == '\0')
{
output[j] = '\0';
cout << output << endl;
return;
}
// recursive case
// here we have two options
// 1. select a single character
int digit = input[i] - '0';
// here comes the tricky part this particular statement
// is how we mapped our input digit with a character
// if digit is 7, then we have ch = 7 + A - 1. Here,
// A will get converted into its ASCII value that is: 65
// hence ch = 65 + 6 that is G
char ch = digit + 'A' - 1;
output[j] = ch;
// now we make the recursive call on the remaining part
// we will call for i + 1 and j + 1 because
// we've read and written only 1 character
generate_strings(input, output, i + 1, j + 1);
// 2. select two digits at a time
if(input[i + 1] != '\0')
{
int digit_1 = input[i] - '0';
int digit_2 = input[i + 1] - '0';
// generate the new number
int digit = digit_1* 10 + digit_2;
if(digit < 27)
{
char _ch = digit + 'A' - 1;
output[j] = _ch;
// here we've used two inputs to create one
// output, hence i = i + 2 and j = j + 1
generate_strings(input, output, i + 2, j + 1);
}
}
return;
}
```

## Generate Strings From Codes Program Using C++

```
#include <iostream>
using namespace std;
void generate_strings(char *input, char *output, int i, int j)
{
// base case
// if we've reached the to NULL character of the input string
if(input[i] == '\0')
{
output[j] = '\0';
cout << output << endl;
return;
}
// recursive case
// here we have two options
// 1. select a single character
int digit = input[i] - '0';
// here comes the tricky part this particular statement
// is how we mapped our input digit with a character
// if digit is 7, then we have ch = 7 + A - 1. Here,
// A will get converted into its ASCII value that is: 65
// hence ch = 65 + 6 that is G
char ch = digit + 'A' - 1;
output[j] = ch;
// now we make the recursive call on the remaining part
// we will call for i + 1 and j + 1 because
// we've read and written only 1 character
generate_strings(input, output, i + 1, j + 1);
// 2. select two digits at a time
if(input[i + 1] != '\0')
{
int digit_1 = input[i] - '0';
int digit_2 = input[i + 1] - '0';
// generate the new number
int digit = digit_1* 10 + digit_2;
if(digit < 27)
{
char _ch = digit + 'A' - 1;
output[j] = _ch;
// here we've used two inputs to create one
// output, hence i = i + 2 and j = j + 1
generate_strings(input, output, i + 2, j + 1);
}
}
return;
}
int main()
{
cout << "Enter the input code" << endl;
char input[100];
cin >> input;
char output[100];
cout << "Possible strings for current code are:" << endl;
generate_strings(input, output, 0, 0);
return 0;
}
```

## Output

## Conclusion

In this article, we learned to develop an algorithm that prints all possible decoded string sequences for a numerical string input. We used recursion and a few ASCII codes concepts to code this algorithm. That’s all for today, thanks for reading.

## Further Readings

If you want to learn more about recursion or dynamic programming, you can refer to the following articles

https://www.journaldev.com/56866/solving-0-n-knapsack-problem-in-cpp

https://www.journaldev.com/58606/fibonacci-series-using-dynamic-programming-cpp