Find all strings formed from characters mapped to digits of a number - GeeksforGeeks

Find all strings formed from characters mapped to digits of a number - GeeksforGeeks
Consider below list where each digit from 1 to 9 maps to few characters.

1 -> ['A', 'B', 'C']
2 -> ['D', 'E', 'F']
3 -> ['G', 'H', 'I']
4 -> ['J', 'K', 'L']
5 -> ['M', 'N', 'O']
6 -> ['P', 'Q', 'R']
7 -> ['S', 'T', 'U']
8 -> ['V', 'W', 'X']
9 -> ['Y', 'Z'] 

Given a number, replace its digits with corresponding characters in given list and print all strings possible. Same character should be considered for every occurrence of a digit in the number. Input number is positive and doesn’t contain 0.

Examples :

Input : 121
Output : ADA BDB CDC AEA BEB CEC AFA BFB CFC

Input : 22
Output : DD EE FF 

The idea is for each digit in the input number, we consider strings formed by previous digit and append characters mapped to current digit to them. If this is not the first occurrence of the digit, we append same character as used in its first occurrence.

vector<string> findCombinations(vector<int> input,

                                vector<char> table[])

{

    // vector of strings to store output

    vector<string> out, temp;

 

    // stores index of first occurrence

    // of the digits in input

    unordered_map<int, int> mp;

 

    // maintains index of current digit considered

    int index = 0;

 

    // for each digit

    for (int d: input)

    {

        // store index of first occurrence

        // of the digit in the map

        if (mp.find(d) == mp.end())

            mp[d] = index;

 

        // clear vector contents for future use

        temp.clear();

 

        // do for each character thats maps to the digit

        for (int i = 0; i < table[d - 1].size(); i++)

        {

            // for first digit, simply push all its

            // mapped characters in the output list

            if (index == 0)

            {

                string s(1, table[d - 1].at(i));

                out.push_back(s);

            }

 

            // from second digit onwards

            if (index > 0)

            {

                // for each string in output list

                // append current character to it.

                for(string str: out)

                {

                    // convert current character to string

                    string s(1, table[d - 1].at(i));

 

                    // Imp - If this is not the first occurrence

                    // of the digit, use same character as used

                    // in its first occurrence

                    if(mp[d] != index)

                        s = str[mp[d]];

 

                    str = str + s;

 

                    // store strings formed by current digit

                    temp.push_back(str);

                }

 

                // nothing more needed to be done if this

                // is not the first occurrence of the digit

                if(mp[d] != index)

                    break;

            }

        }

 

        // replace contents of output list with temp list

        if(index > 0)

            out = temp;

        index++;

    }

 

    return out;

}

Read full article from Find all strings formed from characters mapped to digits of a number - GeeksforGeeks