17. 电话号码的字母组合

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

image.png

示例:

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

说明:

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

思路-回溯法：

回溯是一种通过穷举所有可能的情况来找到解的算法。
定义回溯函数：backtrack(combination, next_digits) ，它将一个目前已经产生的组合combination，和接下来准备要输入的数字字符串next_digits作为参数。
如果没有更多的数字（已经遍历完了所有数字），那就意味着当前的组合已经产生了。将combination添加到组合ans中即可
如果还要数字被输入，则遍历下一个数字对应的每个字母letter：
将当前的字母添加到组合的最后，也就是说combination = combination + letter ，
重复上述过程，继续遍历剩下的数字：backtrack(combination + letter, next_digits[1:]) 。

Java解法：

class Solution {
    Map<String, String> map = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
  }};
    List<String> ans = new ArrayList<String>();
    public void backtrack(String combination, String next_digit)
    {
        int len = next_digit.length();
        if (len == 0)
        {
            ans.add(combination);
        }else{
            String digit = next_digit.substring(0, 1);
            String letters = map.get(digit);
            for(int i = 0; i < letters.length(); i++)
            {
                String curletter = map.get(digit).substring(i, i+1);
                backtrack(combination + curletter, next_digit.substring(1));
            }
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0)
        {
            backtrack("", digits);
        }
        return ans;
    }
}

image.png

python3解法：

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        def backtrack(combination, left_digits):
            # 当数字字符串已经遍历完时，即 backtrack('ad','')
            if not left_digits:
                ans.append(combination)
            #遍历当前数字对应的字符串，例如2，对应a,b,c
            for letter in dic[left_digits[0]]:
                #也就是backtrack('a', '3'),backtrack('b', '3'),backtrack('c', '3')
                backtrack(combination + letter, left_digits[1:])
        # 存储所有字母组合
        ans = []
        if digits:
            backtrack('', digits)
        return ans

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problemset/all/