« Return all codes in string

Problem

Assume that the value of a = 1, b = 2, c = 3, ... , z = 26. You are given a numeric string S. Write a program to return the list of all possible codes that can be generated from the given string.

Note : The order of codes are not important. And input string does not contain 0s.

Input format :

A numeric string

Constraints :

1 <= Length of String S <= 10

Sample Input:

1123

Sample Output:

aabc

kbc

alc

aaw

kw

Solution

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int getAllCodes(string input, string output[])
15{
16    if (input.empty())
17    {
18        output[0] = "";
19        return 1;
20    }
21
22    string output1[10000];
23    char c1 = (input[0] - 48) + 96;
24    int size1 = getAllCodes(input.substr(1), output1);
25    for (int i = 0; i < size1; i++)
26    {
27        output1[i] = c1 + output1[i];
28    }
29
30    int size2 = 0;
31    string output2[10000];
32    if (input.size() > 1)
33    {
34        int d = (input[0] - 48) * 10 + (input[1] - 48);
35        if (d <= 26)
36        {
37            char c2 = 96 + d;
38            size2 = getAllCodes(input.substr(2), output2);
39            for (int i = 0; i < size2; i++)
40            {
41                output2[i] = c2 + output2[i];
42            }
43        }
44    }
45    for (int i = 0; i < size1; i++)
46    {
47        output[i] = output1[i];
48    }
49    for (int i = 0; i < size2; i++)
50    {
51        output[i + size1] = output2[i];
52    }
53
54    return (size1 + size2);
55}
56
57int main()
58{
59    string input;
60    string output[10000];
61    cin >> input;
62
63    int count = getAllCodes(input, output);
64    for (int i = 0; i < count && i < 10000; i++)
65    {
66        cout << output[i] << endl;
67    }
68    return 0;
69}