回溯

• 1、电话号码的字母组合（17）

1、电话号码的字母组合（17）

题目描述：

【中等】

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

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

示例一：

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

题目链接

思路分析

1、对与“23”我们不难推断出它的解为下图：

• 这显然是在树形结构求树叶的全部解，在树形结构中找全部的解，通常使用回溯算法。

2、先写出数字与字符一一映射的字典，phone={‘数字（key）’：‘对应字母（value）’}。

3、定义回溯函数：

即可，当剩余数字长度为0，结束循环，否则，for遍历这个数字的所有字母值，在每个循环中再次进行回溯函数。

定义函数 backtrack(combination, nextdigit)，当 nextdigit 非空时，对于 nextdigit[0] 中的每一个字母 letter，执行回溯 backtrack(combination + letter,nextdigit[1:]，直至 nextdigit 为空。最后将 combination 加入到结果中。

在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。