# Generate Strings From Codes in C++

Filed Under: C++

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.
• 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;
}
```

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