17-电话号码的字母组合

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

---

示例

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

---

解法

核心思想：回溯算法（可当成深度优先的算法）

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # 电话号与九宫格字母相对应
        phone_dict = {'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']}
        # 空字符串
        if not digits:
            return []
        res = []

        # 回溯函数:实现效果是类似深度优先
        def dfs(digits_cut, tmp):
            # 遍历到最后一个字母，返回上一层
            if(digits_cut == ""):
                res.append(tmp)
                return
            for c in phone_dict[digits_cut[0]]:
                # 递归下一位字母
                dfs(digits_cut=digits_cut[1:], tmp=tmp + c)
        # 调用回溯函数
        dfs(digits, "")
        return res

---

来源

LeetCode中该题地址，Click here!