17. 电话号码的字母组合

题目描述

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

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

思路

感觉像是对树的深度优先搜索，假设数字是 23，那它的大概结构是：

flowchart TD
  A["root"]
  A-->B["a"]
  A-->C["b"]
  A-->D["c"]
  B-->E["d"]
  B-->F["e"]
  B-->G["f"]
  C-->H["..."]

这种感觉，首先考虑写一个 DFS：

class Solution:
    tbl = {
        "2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz",
    }
    def letterCombinations(self, digits: str) -> List[str]:
        n = len(digits)
        def dfs(idx):
            if idx == n:
                return
            for ch in self.tbl[digits[idx]]:
                dfs(idx+1)
        dfs(0)

那么接下来考虑怎样保存上一次 dfs 的状态。因为字符串的长度就是 digits 的长度，因此我们可以新建一个临时数组保存当前的树，并在每次更新的是否赋值。那什么时候结束呢？当 idx==n 的时候代表一次 DFS 结束了，此时临时数组的值就是答案（的一部分）。

另外还要注意特殊值，输入为空字符串时返回 []。

最终代码：

class Solution:
    tbl = {
        "2": "abc", "3": "def", "4": "ghi",
        "5": "jkl", "6": "mno", "7": "pqrs",
        "8": "tuv", "9": "wxyz",
    }
    def letterCombinations(self, digits: str) -> List[str]:
        if digits == "":
            return []
        n = len(digits)
        branch = [""] * n
        cmb = []
        def dfs(idx):
            if idx == n:
                cmb.append("".join(branch))
                return
            for ch in self.tbl[digits[idx]]:
                branch[idx]=ch
                dfs(idx+1)
        dfs(0)
        return cmb

想得太多