How can I print out all possible letter combinations a given phone number can represent?

Question

I just tried for my first programming interview and one of the questions was to write a program that given a 7 digit telephone number, could print all possible combinations of letters that each number could represent.

A second part of the question was like what about if this would have been a 12 digit international number? How would that effect your design.

I don't have the code that I wrote in the interview, but I got the impression he wasn't happy with it.
What is the best way to do this?

Answer 1

In Python, iterative:

digit_map = {
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

def word_numbers(input):
  input = str(input)
  ret = ['']
  for char in input:
    letters = digit_map.get(char, '')
    ret = [prefix+letter for prefix in ret for letter in letters]
  return ret

ret is a list of results so far; initially it is populated with one item, the empty string. Then, for each character in the input string, it looks up the list of letters that match it from the dict defined at the top. It then replaces the list ret with the every combination of existing prefix and possible letter.

Answer 2

It is similar to a question called letter combinations of a phone number, here is my solution.
It works for an arbitrary number of digits, so long as the result doesn't exceed the memory limit.

import java.util.HashMap;
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<String>();
        ArrayList<String> preres = new ArrayList<String>();
        res.add("");

        for(int i = 0; i < digits.length(); i++) {
            String letters = map.get(digits.charAt(i));
            if (letters.length() == 0)
                continue;
            for(String str : res) {
                for(int j = 0; j < letters.length(); j++)
                    preres.add(str + letters.charAt(j));
            }
            res = preres;
            preres = new ArrayList<String>();
        }      
        return res;
    }
    
    static final HashMap<Character,String> map = new HashMap<Character,String>(){{
        put('1', "");
        put('2',"abc");
        put('3',"def");
        put('4',"ghi");
        put('5',"jkl");
        put('6',"mno");
        put('7',"pqrs");
        put('8',"tuv");
        put('9',"wxyz");
        put('0', "");
    }} ;
}

I'm not sure how 12-digit international numbers affect the design.

Edit: International numbers will also be handled

Answer 3

In Java using recursion:

import java.util.LinkedList;
import java.util.List;

public class Main {  
    // Number-to-letter mappings in order from zero to nine
    public static String mappings[][] = {
        {"0"}, {"1"}, {"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"}
    };

    public static void generateCombosHelper(List<String> combos, 
            String prefix, String remaining) {
        // The current digit we are working with
        int digit = Integer.parseInt(remaining.substring(0, 1));

        if (remaining.length() == 1) {
            // We have reached the last digit in the phone number, so add 
            // all possible prefix-digit combinations to the list
            for (int i = 0; i < mappings[digit].length; i++) {
                combos.add(prefix + mappings[digit][i]);
            }
        } else {
            // Recursively call this method with each possible new 
            // prefix and the remaining part of the phone number.
            for (int i = 0; i < mappings[digit].length; i++) {
                generateCombosHelper(combos, prefix + mappings[digit][i], 
                        remaining.substring(1));
            }
        }
    }

    public static List<String> generateCombos(String phoneNumber) {
        // This will hold the final list of combinations
        List<String> combos = new LinkedList<String>();

        // Call the helper method with an empty prefix and the entire 
        // phone number as the remaining part.
        generateCombosHelper(combos, "", phoneNumber);

        return combos;
    }

    public static void main(String[] args) {
        String phone = "3456789";
        List<String> combos = generateCombos(phone);

        for (String s : combos) {
            System.out.println(s);
        }
    }
}

Answer 4

The obvious solution is a function to map a digit to a list of keys, and then a function that would generate the possible combinations:

The first is obvious, the second is more problematic because you have around 3^number of digits combinations, which can be a very large number.

One way to do it is to look at each possibility for digit matching as a digit in a number (on base 4) and implement something close to a counter (jumping over some instances, since there are usually less than 4 letters mappable to a digit).

The more obvious solutions would be nested loops or recursion, which are both less elegant, but in my opinion valid.

Another thing for which care must be taken is to avoid scalability issues (e.g. keeping the possibilities in memory, etc.) since we are talking about a lot of combinations.

P.S. Another interesting extension of the question would be localization.

Answer 5

In C++(recursive):

string pattern[] = {"0",".,!","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};
ofstream keyout("keypad.txt");
void print_keypad(char* str, int k, vector<char> patt, int i){
if(str[k] != '\0')
{
    int x = str[k] - '0';
    for(int l = 0; l < pattern[x].length(); l++)
    {
        patt[i] = pattern[x][l];
        print_keypad(str, k+1, patt, i+1);
    }
    keyout << endl;
}
else if(i == k)
{
    string st(patt.data());
    keyout << st << endl;
    return;
}
}

This function can be called with 'k' and 'i' equal to zero.

Anyone, who requires more illustration to understand the logic, can combine recursion technique with following output:

ADG
ADH
ADI

AEG
AEH
AEI

AFG
AFH
AFI


BDG
BDH
BDI

BEG
BEH
BEI

BFG
BFH
...

Answer 6

In numeric keyboards, texts and numbers are placed on the same key. For example 2 has “ABC” if we wanted to write anything starting with ‘A’ we need to type key 2 once. If we wanted to type ‘B’, press key 2 twice and thrice for typing ‘C’. below is picture of such keypad.

keypad http://d2o58evtke57tz.cloudfront.net/wp-content/uploads/phoneKeyboard.png

Given a keypad as shown in diagram, and a n digit number, list all words which are possible by pressing these numbers.

For example if input number is 234, possible words which can be formed are (Alphabetical order): adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Let’s do some calculations first. How many words are possible with seven digits with each digit representing n letters? For first digit we have at most four choices, and for each choice for first letter, we have at most four choices for second digit and so on. So it’s simple maths it will be O(4^n). Since keys 0 and 1 don’t have any corresponding alphabet and many characters have 3 characters, 4^n would be the upper bound of number of words and not the minimum words.

Now let’s do some examples.

For number above 234. Do you see any pattern? Yes, we notice that the last character always either G,H or I and whenever it resets its value from I to G, the digit at the left of it gets changed. Similarly whenever the second last alphabet resets its value, the third last alphabet gets changes and so on. First character resets only once when we have generated all words. This can be looked from other end also. That is to say whenever character at position i changes, character at position i+1 goes through all possible characters and it creates ripple effect till we reach at end. Since 0 and 1 don’t have any characters associated with them. we should break as there will no iteration for these digits.

Let’s take the second approach as it will be easy to implement it using recursion. We go till the end and come back one by one. Perfect condition for recursion. let’s search for base case. When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.When we reach at the last character, we print the word with all possible characters for last digit and return. Simple base case.

Following is C implementation of recursive approach to print all possible word corresponding to a n digit input number. Note that input number is represented as an array to simplify the code.

#include <stdio.h>
#include <string.h>

// hashTable[i] stores all characters that correspond to digit i in phone
const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",
                           "mno", "pqrs", "tuv", "wxyz"};

// A recursive function to print all possible words that can be obtained
// by input number[] of size n.  The output words are one by one stored
// in output[]
void  printWordsUtil(int number[], int curr_digit, char output[], int n)
{
    // Base case, if current output word is prepared
int i;
if (curr_digit == n)
{
    printf("%s ", output);
    return ;
}

// Try all 3 possible characters for current digir in number[]
// and recur for remaining digits
for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)
{
    output[curr_digit] = hashTable[number[curr_digit]][i];
    printWordsUtil(number, curr_digit+1, output, n);
    if (number[curr_digit] == 0 || number[curr_digit] == 1)
        return;
}
}

// A wrapper over printWordsUtil().  It creates an output array and
// calls printWordsUtil()
void printWords(int number[], int n)
{
char result[n+1];
result[n] ='\0';
printWordsUtil(number, 0, result, n);
}

//Driver program
int main(void)
{
int number[] = {2, 3, 4};
int n = sizeof(number)/sizeof(number[0]);
printWords(number, n);
return 0;
}

Output:

adg adh adi aeg aeh aei afg afh afi bdg bdh bdi beg beh bei bfg bfh bfi cdg cdh cdi ceg ceh cei cfg cfh cfi

Time Complexity:

Time complexity of above code is O(4^n) where n is number of digits in input number.

References:

http://www.flipkart.com/programming-interviews-exposed-secrets-landing-your-next-job-3rd/p/itmdxghumef3sdjn?pid=9788126539116&affid=sandeepgfg

Answer 7

In JavaScript. A CustomCounter class takes care of incrementing indexes. Then just output the different possible combinations.

var CustomCounter = function(min, max) {
    this.min = min.slice(0)
    this.max = max.slice(0)
    this.curr = this.min.slice(0)
    this.length = this.min.length
}

CustomCounter.prototype.increment = function() {
    for (var i = this.length - 1, ii = 0; i >= ii; i--) {
        this.curr[i] += 1
        if (this.curr[i] > this.max[i]) {
            this.curr[i] = 0
        } else {
            break
        }
    }
}

CustomCounter.prototype.is_max = function() {
    for (var i = 0, ii = this.length; i < ii; ++i) {
        if (this.curr[i] !== this.max[i]) {
            return false
        }
    }
    return true
}

var PhoneNumber = function(phone_number) {
    this.phone_number = phone_number
    this.combinations = []
}

PhoneNumber.number_to_combinations = {
    1: ['1']
  , 2: ['2', 'a', 'b', 'c']
  , 3: ['3', 'd', 'e', 'f']
  , 4: ['4', 'g', 'h', 'i']
  , 5: ['5', 'j', 'k', 'l']
  , 6: ['6', 'm', 'n', 'o']
  , 7: ['7', 'p', 'q', 'r', 's']
  , 8: ['8', 't', 'u', 'v']
  , 9: ['9', 'w', 'x', 'y', 'z']
  , 0: ['0', '+']
}

PhoneNumber.prototype.get_combination_by_digit = function(digit) {
    return PhoneNumber.number_to_combinations[digit]
}

PhoneNumber.prototype.add_combination_by_indexes = function(indexes) {
    var combination = ''
    for (var i = 0, ii = indexes.length; i < ii; ++i) {
        var phone_number_digit = this.phone_number[i]
        combination += this.get_combination_by_digit(phone_number_digit)[indexes[i]]
    }

    this.combinations.push(combination)
}

PhoneNumber.prototype.update_combinations = function() {
    var min_indexes = []
      , max_indexes = []

    for (var i = 0, ii = this.phone_number.length; i < ii; ++i) {
        var digit = this.phone_number[i]
        min_indexes.push(0)
        max_indexes.push(this.get_combination_by_digit(digit).length - 1)
    }

    var c = new CustomCounter(min_indexes, max_indexes)

    while(true) {
        this.add_combination_by_indexes(c.curr)
        c.increment()

        if (c.is_max()) {
            this.add_combination_by_indexes(c.curr)
            break
        }
    }
}

var phone_number = new PhoneNumber('120')
phone_number.update_combinations()
console.log(phone_number.combinations)

Answer 8

This problem is similar to this leetcode problem. Here is the answer I submitted for this problem to leetcode (check github and video for explanation).

So the very first thing we need is some way to hold the mappings of a digit and we can use a map for this:

private Map<Integer, String> getDigitMap() {
        return Stream.of(
                new AbstractMap.SimpleEntry<>(2, "abc"),
                new AbstractMap.SimpleEntry<>(3, "def"),
                new AbstractMap.SimpleEntry<>(4, "ghi"),
                new AbstractMap.SimpleEntry<>(5, "jkl"),
                new AbstractMap.SimpleEntry<>(6, "mno"),
                new AbstractMap.SimpleEntry<>(7, "pqrs"),
                new AbstractMap.SimpleEntry<>(8, "tuv"),
                new AbstractMap.SimpleEntry<>(9, "wxyz"))
               .collect(Collectors.toMap(AbstractMap.SimpleEntry::getKey, 
                                AbstractMap.SimpleEntry::getValue));
}

The above method is preparing the map and next method I would use is to provide the mapping for provided digit:

private String getDigitMappings(String strDigit, Map<Integer,String> digitMap) {
        int digit = Integer.valueOf(strDigit);
        return digitMap.containsKey(digit) ? digitMap.get(digit) : "";
}

This problem can be solved using backtracking and a backtracking solution generally has a structure where the method signature will contain: result container, temp results, original source with index etc. So the method structure would be of the form:

private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
       // Condition to populate temp value to result
       // explore other arrangements based on the next input digit
       // Loop around the mappings of a digit and then to explore invoke the same method recursively
       // Also need to remove the digit which was in temp at last so as to get proper value in temp for next cycle in loop
}

And now the method body can be filled as (result will be kept in a list, temp in string builder etc.)

private void compute(List<String> result, StringBuilder temp, String digits, int start, Map<Integer, String> digitMap) {
        if(start >= digits.length()) { // condition
            result.add(temp.toString());
            return;
        }

        String letters = getDigitMappings(digits.substring(start, start + 1), digitMap); // mappings of a digit to loop around
        for (int i = 0; i < letters.length(); i++) {
            temp.append(letters.charAt(i));
            compute(result, temp, digits, start+1, digitMap); //explore for remaining digits
            temp.deleteCharAt(temp.length() - 1); // remove last in temp
        }
}

And finally the method can be invoked as:

public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if(digits == null || digits.length() == 0) return result;
        compute(result, new StringBuilder(), digits, 0, getDigitMap());
        return result;
}

Now the max mapped chars for a digit can be 4 (e.g. 9 has wxyz) and backtracking involves exhaustive search to explore all possible arrangements (state space tree) so for a digit of size n we are going to have 4x4x4....n times i.e. complexity would be O(4^n).

Answer 9

namespace WordsFromPhoneNumber
{
    /// <summary>
    /// Summary description for WordsFromPhoneNumber
    /// </summary>
    [TestClass]
    public class WordsFromPhoneNumber
    {
        private static string[] Chars = { "0", "1", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ" };
        public WordsFromPhoneNumber()
        {
            //
            // TODO: Add constructor logic here
            //
        }

        #region overhead

        private TestContext testContextInstance;

        /// <summary>
        ///Gets or sets the test context which provides
        ///information about and functionality for the current test run.
        ///</summary>
        public TestContext TestContext
        {
            get
            {
                return testContextInstance;
            }
            set
            {
                testContextInstance = value;
            }
        }

        #region Additional test attributes
        //
        // You can use the following additional attributes as you write your tests:
        //
        // Use ClassInitialize to run code before running the first test in the class
        // [ClassInitialize()]
        // public static void MyClassInitialize(TestContext testContext) { }
        //
        // Use ClassCleanup to run code after all tests in a class have run
        // [ClassCleanup()]
        // public static void MyClassCleanup() { }
        //
        // Use TestInitialize to run code before running each test 
        // [TestInitialize()]
        // public void MyTestInitialize() { }
        //
        // Use TestCleanup to run code after each test has run
        // [TestCleanup()]
        // public void MyTestCleanup() { }
        //
        #endregion

        [TestMethod]
        public void TestMethod1()
        {
            IList<string> words = Words(new int[] { 2 });
            Assert.IsNotNull(words, "null");
            Assert.IsTrue(words.Count == 3, "count");
            Assert.IsTrue(words[0] == "A", "a");
            Assert.IsTrue(words[1] == "B", "b");
            Assert.IsTrue(words[2] == "C", "c");
        }

        [TestMethod]
        public void TestMethod23()
        {
            IList<string> words = Words(new int[] { 2 , 3});
            Assert.IsNotNull(words, "null");
            Assert.AreEqual(words.Count , 9, "count");
            Assert.AreEqual(words[0] , "AD", "AD");
            Assert.AreEqual(words[1] , "AE", "AE");
            Assert.AreEqual(words[2] , "AF", "AF");
            Assert.AreEqual(words[3] , "BD", "BD");
            Assert.AreEqual(words[4] , "BE", "BE");
            Assert.AreEqual(words[5] , "BF", "BF");
            Assert.AreEqual(words[6] , "CD", "CD");
            Assert.AreEqual(words[7] , "CE", "CE");
            Assert.AreEqual(words[8] , "CF", "CF");
        }

        [TestMethod]
        public void TestAll()
        {
            int[] number = new int [4];
            Generate(number, 0);
        }

        private void Generate(int[] number, int index)
        {
            for (int x = 0; x <= 9; x += 3)
            {
                number[index] = x;
                if (index == number.Length - 1)
                {
                    var w = Words(number);
                    Assert.IsNotNull(w);
                    foreach (var xx in number)
                    {
                        Console.Write(xx.ToString());
                    }
                    Console.WriteLine(" possible words:\n");
                    foreach (var ww in w)
                    {
                        Console.Write("{0} ", ww);
                    }
                    Console.WriteLine("\n\n\n");
                }
                else
                {
                    Generate(number, index + 1);
                }
            }
        }

        #endregion

        private IList<string> Words(int[] number)
        {
            List<string> words = new List<string>(100);
            Assert.IsNotNull(number, "null");
            Assert.IsTrue(number.Length > 0, "length");
            StringBuilder word = new StringBuilder(number.Length);
            AddWords(number, 0, word, words);

            return words;
        }

        private void AddWords(int[] number, int index, StringBuilder word, List<string> words)
        {
            Assert.IsTrue(index < number.Length, "index < length");
            Assert.IsTrue(number[index] >= 0, "number >= 0");
            Assert.IsTrue(number[index] <= 9, "number <= 9");

            foreach (var c in Chars[number[index]].ToCharArray())
            {
                word.Append(c);
                if (index < number.Length - 1)
                {
                    AddWords(number, index + 1, word, words);
                }
                else
                {
                    words.Add(word.ToString());
                }
                word.Length = word.Length - 1;
            }
        }
    }
}

Answer 10

public class Permutation {

    //display all combination attached to a 3 digit number

    public static void main(String ar[]){

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


        int num1, num2, num3=0;
        char tempdata[][]= new char[3][3];
        StringBuilder number = new StringBuilder("324"); // a 3 digit number

        //copy data to a tempdata array-------------------
        num1= Integer.parseInt(number.substring(0,1));
        tempdata[0] = data[num1];
        num2= Integer.parseInt(number.substring(1,2));
        tempdata[1] = data[num2];
        num3= Integer.parseInt(number.substring(2,3));
        tempdata[2] = data[num3];

        //display all combinations--------------------
        char temp2[][]=tempdata;
        char tempd, tempd2;
        int i,i2, i3=0;
        for(i=0;i<3;i++){
                tempd = temp2[0][i];
             for (i2=0;i2<3;i2++){
                 tempd2 = temp2[1][i2];
                 for(i3=0;i3<3;i3++){
                     System.out.print(tempd);
                     System.out.print(tempd2);
                     System.out.print(temp2[2][i3]);
                     System.out.println();
                 }//for i3

            }//for i2
         }
    }

}//end of class

Answer 11

Use a list L where L[i] = the symbols that digit i can represent.

L[1] = @,.,! (for example) L[2] = a,b,c

Etc.

Then you can do something like this (pseudo-C):

void f(int k, int st[])
{
  if ( k > numberOfDigits )
  {
    print contents of st[];
    return;
  }

  for each character c in L[Digit At Position k]
  {
    st[k] = c;
    f(k + 1, st);
  }
}

Assuming each list contains 3 characters, we have 3^7 possibilities for 7 digits and 3^12 for 12, which isn't that many. If you need all combinations, I don't see a much better way. You can avoid recursion and whatnot, but you're not going to get something a lot faster than this no matter what.

Answer 12

#include <sstream>
#include <map>
#include <vector>

map< int, string> keyMap;

void MakeCombinations( string first, string joinThis , vector<string>& eachResult )
{
    if( !first.size() )
        return;

    int length = joinThis.length();
    vector<string> result;

    while( length )
    {
        string each;
        char firstCharacter = first.at(0);
        each =  firstCharacter;
        each += joinThis[length -1];
        length--;

        result.push_back(each);     
    }

    first = first.substr(1);

    vector<string>::iterator begin = result.begin();    
    vector<string>::iterator end = result.end();
    while( begin != end)
    {
        eachResult.push_back( *begin);
        begin++;
    }

    return MakeCombinations( first, joinThis, eachResult);
}


void ProduceCombinations( int inNumber, vector<string>& result)
{
    vector<string> inputUnits;

    int number = inNumber;
    while( number )
    {
        int lastdigit ;

        lastdigit = number % 10;
        number = number/10;
        inputUnits.push_back( keyMap[lastdigit]);
    }

    if( inputUnits.size() == 2)
    {
        MakeCombinations(inputUnits[0], inputUnits[1], result);
    }
    else if ( inputUnits.size() > 2 )
    {
        MakeCombinations( inputUnits[0] , inputUnits[1], result);

        vector<string>::iterator begin = inputUnits.begin();    
        vector<string>::iterator end = inputUnits.end();

        begin += 2;
        while(  begin != end )
        {
            vector<string> intermediate = result;
            vector<string>::iterator ibegin = intermediate.begin(); 
            vector<string>::iterator iend = intermediate.end(); 

            while( ibegin != iend)
            {
                MakeCombinations( *ibegin , *begin, result);
                //resultbegin =  
                ibegin++; 
            }
            begin++;            
        }
    }
    else
    {

    }

    return;
}

int _tmain(int argc, _TCHAR* argv[])
{
    keyMap[1] = "";
    keyMap[2] = "abc";
    keyMap[3] = "def";
    keyMap[4] = "ghi";
    keyMap[5] = "jkl";
    keyMap[6] = "mno";
    keyMap[7] = "pqrs";
    keyMap[8] = "tuv";
    keyMap[9] = "wxyz";
    keyMap[0] = "";

    string  inputStr;
    getline(cin, inputStr);

    int number = 0;

    int length = inputStr.length();

    int tens = 1;
    while( length )
    {
        number += tens*(inputStr[length -1] - '0');
        length--;
        tens *= 10;
    }

    vector<string> r;
    ProduceCombinations(number, r);

    cout << "[" ;

    vector<string>::iterator begin = r.begin(); 
    vector<string>::iterator end = r.end();

    while ( begin != end)
    {
        cout << *begin << "," ;
        begin++;
    }

    cout << "]" ;

    return 0;
}

Answer 13

A Python solution is quite economical, and because it uses generators is efficient in terms of memory use.

import itertools

keys = dict(enumerate('::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ'.split(':')))

def words(number):
    digits = map(int, str(number))
    for ls in itertools.product(*map(keys.get, digits)):
        yield ''.join(ls)

for w in words(258):
    print w

Obviously itertools.product is solving most of the problem for you. But writing it oneself is not difficult. Here's a solution in go, which is careful to re-use the array result to generate all solutions in, and a closure f to capture the generated words. Combined, these give O(log n) memory use inside product.

package main

import (
    "bytes"
    "fmt"
    "strconv"
)

func product(choices [][]byte, result []byte, i int, f func([]byte)) {
    if i == len(result) {
        f(result)
        return
    }
    for _, c := range choices[i] {
        result[i] = c
        product(choices, result, i+1, f)
    }
}

var keys = bytes.Split([]byte("::ABC:DEF:GHI:JKL:MNO:PQRS:TUV:WXYZ"), []byte(":"))

func words(num int, f func([]byte)) {
    ch := [][]byte{}
    for _, b := range strconv.Itoa(num) {
        ch = append(ch, keys[b-'0'])
    }
    product(ch, make([]byte, len(ch)), 0, f)
}

func main() {
    words(256, func(b []byte) { fmt.Println(string(b)) })
}

Answer 14

This is the C# port of this answer.

Code

public class LetterCombinations
{
    private static readonly Dictionary<string, string> Representations = new Dictionary<string, string>
    {
       {"2", "abc" },
       {"3", "def" },
       {"4", "ghi" },
       {"5", "jkl" },
       {"6", "mno" },
       {"7", "pqrs" },
       {"8", "tuv" },
       {"9", "wxyz" },
    };

    public static List<string> FromPhoneNumber(string phoneNumber)
    {
        var result = new List<string> { string.Empty };

        // go through each number in the phone
        for (int i = 0; i < phoneNumber.Length; i++)
        {
            var pre = new List<string>();
            foreach (var str in result)
            {
                var letters = Representations[phoneNumber[i].ToString()];
                // go through each representation of the number
                for (int j = 0; j < letters.Length; j++)
                {
                    pre.Add(str + letters[j]);
                }
            }
            result = pre;
        }

        return result;
    }
}

Unit Tests

public class UnitTest
{
    [TestMethod]
    public void One_Digit_Yields_Three_Representations()
    {
        var sut = "2";

        var expected = new List<string>{ "a", "b", "c" };
        var actualResults = LetterCombinations.FromPhoneNumber(sut);

        CollectionAssert.AreEqual(expected, actualResults);
    }

    [TestMethod]
    public void Two_Digits_Yield_Nine_Representations()
    {
        var sut = "22";

        var expected = new List<string> { "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" };
        var actualResults = LetterCombinations.FromPhoneNumber(sut);

        CollectionAssert.AreEqual(expected, actualResults);
    }

    [TestMethod]
    public void Three_Digits_Yield_ThirtyNine_Representations()
    {
        var sut = "222";

        var actualResults = LetterCombinations.FromPhoneNumber(sut);

        var possibleCombinations = Math.Pow(3,3); //27

        Assert.AreEqual(possibleCombinations, actualResults.Count);
    }
}

Answer 15

Python solution with

def keypad_words(number):
    
    num_pad_dict = {
        '2': ['a', 'b', 'c'],
        '3': ['d', 'e', 'f'],
        '4': ['g', 'h', 'i'],
        '5': ['j', 'k', 'l'],
        '6': ['m', 'n', 'o'],
        '7': ['p', 'q', 'r', 's'],
        '8': ['t', 'u', 'v'],
        '9': ['w', 'x', 'y', 'z'],
    }
    result = num_pad_dict.get(number[0], '')
    for i in range(1,len(number)):
        letters = num_pad_dict.get(number[i], '')
        new_result = []
        for prefix in result:  
            for letter in letters:
                new_result.append(prefix+letter)   
            
        result = new_result
    return result
    return []