17. Letter Combinations of a Phone Number

Given a digit string, 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.

Input:Digit string "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:

Method 1: Recursive

The idea is use DFS to try all possible combinations till the string size equals to the digits size.

The time complexity is O(mⁿ), where m is the number of choices for each number, and n is the length of the digits.



Code:

public class Solution {
    private final String[] keys = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        helper(digits, result, "", 0);
        return result;
    }
    
    public void helper(String digits, List<String> result, String str, int pos) {
        if (pos == digits.length()) {
            result.add(str);
            return;
        }
        
        String letter = keys[digits.charAt(pos) - '0'];
        for (int i = 0; i < letter.length(); i++) {
            helper(digits, result, str + letter.charAt(i), pos + 1);
        }
    }
}

Method 2: Iterative

We use a queue to store the candidates with length i.

In each iteration, we poll the candidates with length i, add a new character, and add back to the queue.

After n iterations, all candidates in the queue have length n.

The time complexity is also O(mⁿ).



Code:

public class Solution {
    
    private final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer("");
        for (int i = 0; i < digits.length(); i++) {
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                String str = queue.poll();
                for (int k = 0; k < KEYS[digits.charAt(i) - '0'].length(); k++) {
                    queue.offer(str + KEYS[digits.charAt(i) - '0'].charAt(k));
                }
            }
        }
        result.addAll(queue);
        return result;
    }
}