[LeetCode] 17. Letter Combinations of a Phone Number

Posted on | In

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.

17. Letter Combinations of a Phone Number

Example:

1
2
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.

Explanation

  1. We can use DFS to solve this problem.

  2. If the input is "23", then we can draw the following tree:

1
2
3
                            root
     level0:         a       b       c
     level1:       d e f   d e f   d e f

  1. When using DFS, we need to think of the base case. The base case is when the level reaching the end, in this case when we reaches level 2, we already got ad, then we need to append it to the result and return.

  2. In this case, we will get ad, append to the res, then remove the d; we then get ae, append to the res, then remove the e; we then get af, append to the res, then remove the f. Now we finish looping level1, we return back to level 0. Then remove the a, looping to the next char b and repeat.

Solution

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
class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if (digits.length() < 1) return res;
        StringBuilder temp = new StringBuilder();
        HashMap<Character, String> hm = new HashMap<>();
        hm.put('2', "abc");
        hm.put('3', "def");
        hm.put('4', "ghi");
        hm.put('5', "jkl");
        hm.put('6', "mno");
        hm.put('7', "pqrs");
        hm.put('8', "tuv");
        hm.put('9', "wxyz");
        dfs(digits, 0, hm, temp, res);
        return res;
    }
    
    void dfs(String digits, int level, HashMap<Character, String> hm, StringBuilder temp, List<String> res) {
        if (level == digits.length()) {
            res.add(temp.toString());
            return;
        }

        String str = hm.get(digits.charAt(level));
        for (char ch : str.toCharArray()) {
            temp.append(ch);
            dfs(digits, level+1, hm, temp, res);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}