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

0 0 9 minutes read

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 the previous digit and append characters mapped to the current digit to them. If this is not the first occurrence of the digit, we append the same character as used in its first occurrence.

Implementation:

C++

// C++ program to find all strings formed from a given
// number where each digit maps to given characters.
#include <bits/stdc++.h>
using namespace std;
 
// Function to find all strings formed from a given
// number where each digit maps to given characters.
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 that 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;
}
 
// Driver program
int main()
{
    // vector to store the mappings
    vector<char> table[] =
    {
        { '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' }
    };
 
    // vector to store input number
    vector<int> input = { 1, 2, 1};
 
    vector<string> out = findCombinations(input, table);
 
    // print all possible strings
    for (string it: out)
        cout << it << " ";
 
    return 0;
}

Java

// Java Program for the above approach
 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
 
public class Main {
    // Function to find all strings formed from a given
    // number where each digit maps to given characters.
    public static List<String> findCombinations(List<Integer> input, 
                  List<Character>[] table) {
        // list of strings to store output
        List<String> out = new ArrayList<>();
        List<String> temp = new ArrayList<>();
 
        // stores index of first occurrence
        // of the digits in input
        Map<Integer, Integer> mp = new HashMap<>();
 
        // 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.containsKey(d))
                mp.put(d, index);
 
            // clear list contents for future use
            temp.clear();
 
            // do for each character that maps to the digit
            for (int i = 0; i < table[d - 1].size(); i++) {
                // for first digit, simply add all its
                // mapped characters in the output list
                if (index == 0) {
                    out.add(Character.toString(table[d - 1].get(i)));
                }
 
                // 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 = Character.toString(table[d - 1].get(i));
 
                        // Imp - If this is not the first occurrence
                        // of the digit, use same character as used
                        // in its first occurrence
                        if (mp.get(d) != index)
                            s = Character.toString(str.charAt(mp.get(d)));
 
                        str = str + s;
 
                        // store strings formed by current digit
                        temp.add(str);
                    }
 
                    // nothing more needed to be done if this
                    // is not the first occurrence of the digit
                    if (mp.get(d) != index)
                        break;
                }
            }
 
            // replace contents of output list with temp list
            if (index > 0)
                out = new ArrayList<>(temp);
            index++;
        }
 
        return out;
    }
 
    // Driver program
    public static void main(String[] args) {
        // list to store the mappings
        List<Character>[] table = new ArrayList[] {
                new ArrayList<>(List.of('A', 'B', 'C')),
                new ArrayList<>(List.of('D', 'E', 'F')),
                new ArrayList<>(List.of('G', 'H', 'I')),
                new ArrayList<>(List.of('J', 'K', 'L')),
                new ArrayList<>(List.of('M', 'N', 'O')),
                new ArrayList<>(List.of('P', 'Q', 'R')),
                new ArrayList<>(List.of('S', 'T', 'U')),
                new ArrayList<>(List.of('V', 'W', 'X')),
                new ArrayList<>(List.of('Y', 'Z'))
        };
 
        // list to store input number
        List<Integer> input = List.of(1, 2, 1);
 
        List<String> out = findCombinations(input, table);
 
        // print all possible strings
        for (String str : out)
            System.out.print(str + " ");
    }
}
 
// This code is contributed by adityasharmadev01

Python3

# Python program to find all strings formed from a given
# number where each digit maps to given characters.
 
# Function to find all strings formed from a given
# number where each digit maps to given characters.
def findCombinations(input: list, table: list) -> list:
 
    # vector of strings to store output
    out, temp = [], []
 
    # stores index of first occurrence
    # of the digits in input
    mp = dict()
 
    # maintains index of current digit considered
    index = 0
 
    # for each digit
    for d in input:
 
        # store index of first occurrence
        # of the digit in the map
        if d not in mp:
            mp[d] = index
 
        # clear vector contents for future use
        temp.clear()
 
        # do for each character that maps to the digit
        for i in range(len(table[d - 1])):
 
            # for first digit, simply push all its
            # mapped characters in the output list
            if index == 0:
                s = table[d - 1][i]
                out.append(s)
 
            # from second digit onwards
            if index > 0:
 
                # for each string in output list
                # append current character to it.
                for string in out:
 
                    # convert current character to string
                    s = table[d - 1][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 = string[mp[d]]
 
                    string = string + s
 
                    # store strings formed by current digit
                    temp.append(string)
 
                # 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.copy()
        index += 1
    return out
 
# Driver Code
if __name__ == "__main__":
 
    # vector to store the mappings
    table = [['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']]
 
    # vector to store input number
    input = [1, 2, 1]
    out = findCombinations(input, table)
 
    # print all possible strings
    for it in out:
        print(it, end=" ")
 
# This code is contributed by
# sanjeev2552

C#

using System;
using System.Collections.Generic;
 
class Program
{
  // Function to find all strings formed from a given
  // number where each digit maps to given characters.
  static List<string> findCombinations(List<int> input, List<char>[] table)
  {
    // list of strings to store output
    List<string> outList = new List<string>();
    List<string> tempList;
 
    // stores index of first occurrence
    // of the digits in input
    Dictionary<int, int> mp = new Dictionary<int, int>();
 
    // maintains index of current digit considered
    int index = 0;
 
    // for each digit
    foreach (int d in input)
    {
      // store index of first occurrence
      // of the digit in the map
      if (!mp.ContainsKey(d))
      {
        mp[d] = index;
      }
 
      // clear list contents for future use
      tempList = new List<string>();
 
      // do for each character that maps to the digit
      for (int i = 0; i < table[d - 1].Count; i++)
      {
        // for first digit, simply add all its
        // mapped characters in the output list
        if (index == 0)
        {
          string s = table[d - 1][i].ToString();
          outList.Add(s);
        }
 
        // from second digit onwards
        if (index > 0)
        {
          // for each string in output list
          // append current character to it.
          foreach (string str in outList)
          {
            // convert current character to string
            string s = table[d - 1][i].ToString();
 
            // 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]].ToString();
            }
 
            // store strings formed by current digit
            string newStr = str + s;
            tempList.Add(newStr);
          }
 
          // 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)
      {
        outList = tempList;
      }
      index++;
    }
 
    return outList;
  }
 
  // Driver program
  static void Main()
  {
    // list to store the mappings
    List<char>[] table =
    {
      new List<char>{ 'A', 'B', 'C' },
      new List<char>{ 'D', 'E', 'F' },
      new List<char>{ 'G', 'H', 'I' },
      new List<char>{ 'J', 'K', 'L' },
      new List<char>{ 'M', 'N', 'O' },
      new List<char>{ 'P', 'Q', 'R' },
      new List<char>{ 'S', 'T', 'U' },
      new List<char>{ 'V', 'W', 'X' },
      new List<char>{ 'Y', 'Z' }
    };
 
    // list to store input number
    List<int> input = new List<int> { 1, 2, 1 };
 
    List<string> outList = findCombinations(input, table);
 
    // print all possible strings
    foreach (string s in outList)
    {
      Console.Write(s + " ");
    }
  }
}

Javascript

<script>
 
// JavaScript program to find all strings formed from a given
// number where each digit maps to given characters.
 
// Function to find all strings formed from a given
// number where each digit maps to given characters.
function findCombinations(input,table)
{
 
    // vector of strings to store output
    let out = [], temp = [];
 
    // stores index of first occurrence
    // of the digits in input
    let mp = new Map();
 
    // maintains index of current digit considered
    let index = 0;
 
    // for each digit
    for (let d of input)
    {
        // store index of first occurrence
        // of the digit in the map
        if (mp.has(d) == false)
            mp.set(d , index);
 
        // clear vector contents for future use
        temp = [];
 
        // do for each character that maps to the digit
        for (let i = 0; i < table[d - 1].length; i++)
        {
            // for first digit, simply push all its
            // mapped characters in the output list
            if (index == 0)
            {
                let s = table[d - 1][i];
                out.push(s);
            }
 
            // from second digit onwards
            if (index > 0)
            {
                // for each string in output list
                // append current character to it.
                for(let str of out)
                {
                    // convert current character to string
                    let s = table[d - 1][i];
 
                    // Imp - If this is not the first occurrence
                    // of the digit, use same character as used
                    // in its first occurrence
                    if(mp.get(d) != index)
                        s = str[mp.get(d)];
 
                    str = str + s;
 
                    // store strings formed by current digit
                    temp.push(str);
                }
 
                // nothing more needed to be done if this
                // is not the first occurrence of the digit
                if(mp.get(d) != index)
                    break;
            }
        }
 
        // replace contents of output list with temp list
        if(index > 0)
            out = temp;
        index++;
    }
 
    return out;
}
 
// Driver program
 
// vector to store the mappings
let table = [
        [ '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' ]
    ];
 
    // vector to store input number
let input = [ 1, 2, 1 ];
 
let out = findCombinations(input, table);
 
// print all possible strings
for (let it of out)
    document.write(it , " ");
 
// This code is contributed by shinjanpatra
 
</script>

Output

ADA BDB CDC AEA BEB CEC AFA BFB CFC

This article is contributed by Aditya Goel. If you like zambiatek and would like to contribute, you can also write an article and mail your article to review-team@zambiatek.com. See your article appearing on the zambiatek main page and help other Geeks.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!