Problem
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
2 - abc, 3 - def, 4 - ghi, 5 - jkl, 6 - mno, 7 - pqrs, 8 - tuv, 9 - wxyz
Example:
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
Solution
This is to enumerate all the possible combinations. If we know k digits we will have, we can write a k layer loop to enumerate all the possibilities. However, we don't know how many layers of loop we need to write. That means we might need to use recursive to figure out the solution. Brutal force or not, the enumerate need to visit 3^M * 4^N possible combinations, that gives the time cost. We need to store all those 3^M * 4^N possible combinations, that gives us the space cost.
A technique called backtracing can allow us to store temporary strings in recursive call stacks, then only add the final string to result set. The exit condition for backtracing is the temporary string length is equal to the digit length.
import java.util.*;
class DigitsToWords {
private List<String> result = new ArrayList<>();
private Map<Character, String> keyboard = new HashMap<>();
public DigitsToWords() {
keyboard.put('2', "abc");
keyboard.put('3', "def");
keyboard.put('4', "ghi");
keyboard.put('5', "jkl");
keyboard.put('6', "mno");
keyboard.put('7', "pqrs");
keyboard.put('8', "tuv");
keyboard.put('9', "wxyz");
}
public static void main(String...args) {
DigitsToWords dtw = new DigitsToWords();
dtw.toWords(23);
for(String word : dtw.result) {
System.out.print(word + " ");
}
}
//"23"
public void toWords(int number) {
String word = "";
String digits = "" + number;
convert("", digits, 0);
}
/*
convert("", "23", 0)
convert("a", "23", 1)
convert("ad", "23", 2)
convert("ae", "23", 2)
convert("af", "23", 2)
convert("b", "23", 1)
convert("c", "23", 1)
*/
private void convert(String prefix, String digits, int d) {
if(prefix.length() == digits.length()) {
result.add(prefix);
} else {
String tmp = keyboard.get(digits.charAt(d));//"abc", "def"
for(char c : tmp.toCharArray()) {
convert(prefix + c, digits, d + 1);
}
}
}
}
class DigitsToWords {
private List<String> result = new ArrayList<>();
private Map<Character, String> keyboard = new HashMap<>();
public DigitsToWords() {
keyboard.put('2', "abc");
keyboard.put('3', "def");
keyboard.put('4', "ghi");
keyboard.put('5', "jkl");
keyboard.put('6', "mno");
keyboard.put('7', "pqrs");
keyboard.put('8', "tuv");
keyboard.put('9', "wxyz");
}
public static void main(String...args) {
DigitsToWords dtw = new DigitsToWords();
dtw.toWords(23);
for(String word : dtw.result) {
System.out.print(word + " ");
}
}
//"23"
public void toWords(int number) {
String word = "";
String digits = "" + number;
convert("", digits, 0);
}
/*
convert("", "23", 0)
convert("a", "23", 1)
convert("ad", "23", 2)
convert("ae", "23", 2)
convert("af", "23", 2)
convert("b", "23", 1)
convert("c", "23", 1)
*/
private void convert(String prefix, String digits, int d) {
if(prefix.length() == digits.length()) {
result.add(prefix);
} else {
String tmp = keyboard.get(digits.charAt(d));//"abc", "def"
for(char c : tmp.toCharArray()) {
convert(prefix + c, digits, d + 1);
}
}
}
}
Time cost O(3^M * 4^N) where M is the number of digits mapping to 3 letter ones and N is the number of digits mapping to 4 letter ones.
The space cost is O(3^M * 4^N) as well.
