Question: Suppose you represent every number with a character like

0 –> a, 1 –> b, 2 –> c, ………………24 –> y, 25 –> z

Now given a number, give words combinations for it.

Example: 1234
=> 1-2-3-4, 12-2-4, 1-23-4
=> bcde, mde, bxe

Answer: As we are seeing in example, we can see that every time we can club at most 2 numbers at a time. And that too only if they form a number less than 25 (=> z). Now if we divide this problem in sub-problems (sub string) and append the result of second part to result of first part recursively, whoa! We are done.

Example: Lets say our input is “121324”, and our generation function is Calculate(), then output will be like:

This process will stop, once we reach the last character in input string. Now this is a simple recursion now, with few things in mind:

  1. Recursion will stop once we reach the last character in input string.
  2. While we are combining 2 characters, we should take care that it doesn’t exceed 25.
Code:

//  1234 => 1-2-3-4, 12-2-4, 1-23-4 => bcde, mde, bxe

#include <iostream>
using namespace std;

char arr[] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

char input[100];
int len;

void print_combination(int index, char out[], int outindex)
{
  if(index == len){
  out[outindex] = '\0';
  cout << out << endl;
  return;
 }
  
 if(index <= (len - 1)){
  out[outindex] = arr[int(input[index]) - 48];
  print_combination(index+1, out, outindex+1);
 }

  if(index <= (len - 2)){
  int num = (int(input[index])-48)*10 + (int(input[index+1])-48);  
    if (num <= 25){
   out[outindex] = arr[num];
   print_combination(index+2, out, outindex+1);
  }
 }
}

int main(int argc, char* argv[])
{
 char out[100] = {'\0',};
 
 if (argc < 2)
  exit(0);
 else 
  strcpy(input,argv[1]);
  
 len = strlen(input); 
 print_combination(0, out, 0);
}
Update: We can also consider memoization to save repetitive call for same substring.

Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.