題目

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.

思路：可以使用遞歸的方式來解決此題。

public List<String> letterCombinations(String digits) {
        List<String> rec = new ArrayList<String>();
        if (digits == null || digits.length() == 0) {
            return rec;
        }

        String[] letters = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder string = new StringBuilder();

        lettersCombinations(digits, letters, 0, rec, string);
        return rec;
    }

public void lettersCombinations(String digits, String[] letters, int number, List<String> rec, StringBuilder string) {
        if (digits.length() == number) {
            rec.add(string.toString());
            return;
        }

        String letter = letters[digits.charAt(number) - '2'];

        for (int i = 0; i < letter.length(); i++) {
            string.append(letter.charAt(i));
            lettersCombinations(digits, letters, number + 1, rec, string);
            string.deleteCharAt(string.length() - 1);
        }

    }