17. 电话号码的字母组合

给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i]是范围['2', '9']的一个数字。

Python:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        adic = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'}
        res = []
        def dfs(word, i):
            if not digits:
                return 
            if i == len(digits):
                res.append(word)
                return 
            temp = adic[digits[i]]
            for char in temp:
                word += char
                dfs(word, i+1)
                word = word[:-1]
        dfs("", 0)
        return res

Java:

class Solution {
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> result = new ArrayList<String>();
        if(digits.length() == 0)
            return result;
        else
            dfs(result, map, digits, new StringBuilder(), 0);
        return result;
    }

    public void dfs(List<String> result, Map<Character, String> map, String digits, StringBuilder temp, int index)
    {
        // System.out.println(temp);
        if(index == digits.length())
        {
            result.add(temp.toString());
            return;
        }
        String alpha = map.get(digits.charAt(index));
        for(int j = 0; j < alpha.length(); j++)
        {
            temp.append(alpha.charAt(j));
            dfs(result, map, digits, temp, index+1);
            temp.deleteCharAt(temp.length()-1);
        }
    }
}