[LeetCode] Problem 17 - Letter Combinations of a Phone Number

Posted on | In ,

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.

k5iEQ0.png

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Map<Character, char[]> map = new HashMap<Character, char[]>() {{
    put('2', new char[] { 'a', 'b', 'c' });
    put('3', new char[] { 'd', 'e', 'f' });
    put('4', new char[] { 'g', 'h', 'i' });
    put('5', new char[] { 'j', 'k', 'l' });
    put('6', new char[] { 'm', 'n', 'o' });
    put('7', new char[] { 'p', 'q', 'r', 's' });
    put('8', new char[] { 't', 'u', 'v' });
    put('9', new char[] { 'w', 'x', 'y', 'z' });
}};

public List<String> letterCombinations(String digits) {
    List<String> result = new ArrayList<>();

    if (digits == null || digits.length() < 1) 
        return result;
    
    StringBuilder sb = new StringBuilder();
    combinationHelper(result, digits, sb);

    return result;
}

private void combinationHelper(List<String> result, String digits, StringBuilder sb) {
    if (sb.length() == digits.length()) {
        result.add(sb.toString());
        return;
    }

    for (char c : map.get(digits.charAt(sb.length()))) {
        sb.append(c);
        combinationHelper(result, digits, sb);
        sb.deleteCharAt(sb.length() - 1);
    }
}