题目

给定一个仅包含数字 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'] 的一个数字。

  方案一（回溯）

  ```go var m map[string][]string = map[string][]string { “2”: []string{“a”, “b”, “c”}, “3”: []string{“d”, “e”, “f”}, “4”: []string{“g”, “h”, “i”}, “5”: []string{“j”, “k”, “l”}, “6”: []string{“m”, “n”, “o”}, “7”: []string{“p”, “q”, “r”, “s”}, “8”: []string{“t”, “u”, “v”}, “9”: []string{“w”, “x”, “y”, “z”}, }

func letterCombinations(digits string) []string { if digits == “” { return []string{} }

var res []string
dfs(digits, "", &res)
return res

}

func dfs(digits string, path string, res []string) { if digits == “” { res = append(*res, path) return }

for _, alpha := range m[string(digits[0])] {
    dfs(digits[1:], path + alpha, res)
}

}

<a name="BkLqm"></a>
# 方案二（递归）
```python
class Solution:
    def __init__(self):
        self.map = {
            "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 letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
        if len(digits) == 1:
            return self.map[digits]

        # 前 i 个 digits 组成的 ret
        res = self.letterCombinations(digits[:-1])

        ret = []
        for each in res:
            for word in self.map[digits[-1]]:
                ret.append(each + word)

        return ret

原文

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/