12,699,054 members (24,465 online)
Tip/Trick
alternative version

19.1K views
9 bookmarked
Posted

# Algorithm: Get all possible letter combinations from a dialed number

, 15 Sep 2011 CPOL
 Rate this:

### 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).

## You may also be interested in...

 First Prev Next
 Reason for my vote of 5 Cool app Shahare19-Sep-11 20:27 Shahare 19-Sep-11 20:27
 Reason for my vote of 5 Clean and very cool Chris Portela19-Sep-11 16:14 Chris Portela 19-Sep-11 16:14
 Reason for my vote of 4 Simple, straightforward and well wri... BrianBissell19-Sep-11 4:29 BrianBissell 19-Sep-11 4:29
 Last Visit: 31-Dec-99 19:00     Last Update: 22-Jan-17 4:48 Refresh 1