Click here to Skip to main content
Click here to Skip to main content

Algorithm: Get all possible letter combinations from a dialed number

, 15 Sep 2011 CPOL
Rate this:
Please Sign up or sign in to vote.

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].

License

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

Share

About the Author

ludovicianul
Technical Lead Endava Ltd.
Romania Romania
My name is Madalin Ilie. Currently I'm a Development Lead at Endava Romania (www.endava.com).
Follow on   Twitter

Comments and Discussions

 
GeneralReason for my vote of 5 Cool app PinmemberShahare19-Sep-11 20:27 
GeneralReason for my vote of 5 Clean and very cool PinmemberChris Portela19-Sep-11 16:14 
GeneralReason for my vote of 4 Simple, straightforward and well wri... PinmemberBrianBissell19-Sep-11 4:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.1411023.1 | Last Updated 15 Sep 2011
Article Copyright 2011 by ludovicianul
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid