/ Data Structure and Algorithms  

Leetcode 17. Letter Combinations of a Phone Number

Question



Given a string of numbers, each number can represent several letters under a number key. Return all possible composition of the letters under these numbers.

Similar Questions

Soultion

Think of the string 23 as ["a", "b", c] * ["d", "e", "f"], and multiplication can be achieved with two for loops. See the code. Should be easy enough to understand.

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
36
37
38
39
40
public List<String> letterCombinations(String digits) {
    if (digits.length() == 0) {
        return new ArrayList<>();
    }

    char[] digitsChar = digits.toCharArray();

    // define the mapping relationship between number and char
    Map<Integer, List<String>> keyMap = new HashMap<>();
    keyMap.put(2, Arrays.asList("a", "b", "c"));
    keyMap.put(3, Arrays.asList("d", "e", "f"));
    keyMap.put(4, Arrays.asList("g", "h", "i"));
    keyMap.put(5, Arrays.asList("j", "k", "l"));
    keyMap.put(6, Arrays.asList("m", "n", "o"));
    keyMap.put(7, Arrays.asList("p", "q", "r", "s"));
    keyMap.put(8, Arrays.asList("t", "u", "v"));
    keyMap.put(9, Arrays.asList("w", "x", "y", "z"));

    List<String> result = new ArrayList<>(keyMap.get(Character.getNumericValue(digitsChar[0])));

    for (int i = 1; i < digitsChar.length; i++) {
        int digit = Character.getNumericValue(digitsChar[i]);

        result = multipleStrings(result, keyMap.get(digit));
    }

    return result;
}

private List<String> multipleStrings(List<String> a, List<String> b) {
    List<String> result = new ArrayList<>();

    for (String tempA : a) {
        for (String tempB : b) {
            result.add(tempA + tempB);
        }
    }

    return result;
}

Solution - Iteration

Mainly used LinkedList

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
LinkedList<String> result = new LinkedList<>();

if (digits.length() == 0) {
    return result;
}

String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

result.add("");

for (int i = 0; i < digits.length(); i++) {
    int x = Character.getNumericValue(digits.charAt(i));

    // check the length of elements at the head of the list
    while (result.peek().length() == i) {
        String temp = result.remove();

        for (char c : mapping[x].toCharArray()) {
            result.add(temp + c);
        }
    }
}

return result;

If it is 23, then:

result becomes a, b, c after the first for loop ends;

The 1st while loop of the second for loop pop a out, adds d, e, f and joins with a. result becomes b c ad ae af

The 2nd while loop of the second for loop pop b out, adds d, e, f and joins with b. result becomes c ad ae af bd be bf

The 3rd while loop of the second for loop pop c out, adds d, e, f and joins with c, result becomes ad ae af bd be bf cd ce cf

In this case, the element length of the queue is no longer equal to 1, and the while loop is out.