Algorithm: Get all possible letter combinations from a dialed number

Problem

Implement a smart dialer. When typing digits into a dialer, get all contacts that match any letters combination corresponding to the typed digits. If you type 564, for example, the dialer should suggest John.

Solution

The core of this dialer is an algorithm that returns all possible letter combinations for a dialed number. After this, just find any contact that starts with any of this combinations.

How to do it:

• We need a mapping between digits and letters.
• If the dialed number starts with 0 or 1, ignore it as they don't match any letter on the keyboard
• Otherwise, for each digit in the dialed number, iterate through each array of letters and put each possible combination into a list.

This can be implemented using recursion. The code in Java (for Android):

package insidecoding.android;

import java.util.ArrayList;
import java.util.List;

public class DialSuggestHelper {
    private static final 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" }, { "X", "Y", "Z", "W" } };

    private DialSuggestHelper() {

    }

    public static List getConditions(String number) {
        if (number.startsWith("0") || number.startsWith("1")) {
            return new ArrayList();
        }

        List list = new ArrayList();

        int[] arr = new int[number.length()];
        for (int j = 0; j < arr.length; j++) {
            arr[j] = Integer.parseInt(String.valueOf(number.charAt(j)));
        }
        combine("", arr, 0, list);
        return list;
    }

    public static void combine(String root, int[] number, int current,
            List list) {
        for (int k = 0; k < MAPPINGS[number[current]].length; k++) {

            if (current == number.length - 1) {
                list.add(root + MAPPINGS[number[current]][k]);
            } else {
                combine(root + MAPPINGS[number[current]][k], number, current + 1,
                        list);
            }

        }
    }
}

Usage: getConditions("564") will return [JMG, JMH, JMI, JNG, JNH, JNI, JOG, JOH, JOI,
KMG, KMH, KMI, KNG, KNH, KNI, KOG, KOH, KOI, LMG,
LMH, LMI, LNG, LNH, LNI, LOG, LOH, LOI].