Leetcode: 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.

Understand the problem:
The problem gives a digit string, return all possible letter combination that the number could represent. Note the the relative order of the number should be reflated in the corresponding strings. For instance, "23", 2 is ahead of 3, so abc should be in front of def as well. For a brute force solution, we can iterate all possible combinations, with the time complexity of O(n^m), where n is the number of characters for each digit, m is the length of the digit string. 

Recursive Solution:
It is a typical recursive problem, you can mimic the solution of Subset. 

Code (Java):

public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        
        if (digits == null) return result;
        
        String[] dict = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        
        StringBuilder sb = new StringBuilder();
        letterCombinationsHelper(digits, 0, sb, dict, result);
        
        return result;
    }
    
    private void letterCombinationsHelper(String digits, int start, StringBuilder temp, String[] dict, ArrayList<String> result) {
        if (start >= digits.length()) {
            result.add(temp.toString());
            return;
        }
        
        // char to int
        int num = digits.charAt(start) - '0';
        for (int i = 0; i < dict[num].length(); i++) {
            temp.append(dict[num].charAt(i));
            letterCombinationsHelper(digits, start + 1, temp, dict, result);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

Summary:
This is a very classical permutation and combination problem. All P&C problems share the similar idea of using DFS. Be cautious about that.