1

Generate Strings From Codes in C++

 2 years ago
source link: https://www.journaldev.com/59833/generate-strings-from-codes-cpp
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

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

Generate Strings OutputGenerate Strings 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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK