Click here to Skip to main content
65,938 articles
CodeProject is changing. Read more.
Articles / Mobile / Android

Algorithm: Get all possible letter combinations from a dialed number

4.89/5 (9 votes)
15 Sep 2011CPOL 30.9K  

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):
Java
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].

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)