14,327,936 members

Algorithm: Get all possible letter combinations from a dialed number

Rate this:
15 Sep 2011CPOL

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) {
} 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].

Share

My name is Madalin Ilie. Currently I'm a Development Lead at Endava Romania (www.endava.com).

 First Prev Next
 Reason for my vote of 5 Cool app Shahare19-Sep-11 19:27 Shahare 19-Sep-11 19:27
 Reason for my vote of 5 Clean and very cool Chris Portela19-Sep-11 15:14 Chris Portela 19-Sep-11 15:14
 Reason for my vote of 4 Simple, straightforward and well wri... BrianBissell19-Sep-11 3:29 BrianBissell 19-Sep-11 3:29
 Last Visit: 16-Oct-19 1:45     Last Update: 16-Oct-19 1:45 Refresh 1

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

Tip/Trick
Posted 12 Sep 2011

26.1K views
9 bookmarked