# 第79期-基础算法：回溯电话号码的字母组合

Python是一门需要不断实践练习的编程语言，本文档将AI大学堂学员交流群的Python每周练习进行汇总，希望各位小伙伴能够多进行实践练习，逐渐爱上这门神奇的编程语言，掌握它并在生活中能够使用它。

# 1 问题描述

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

示例 1:

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

示例 2:

输入: digits = ""
输出: []

示例 3:

输入: digits = "2"
输出: ["a","b","c"]

初始代码

from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        #在此之间填写代码

print(Solution().letterCombinations("23"))
print(Solution().letterCombinations(""))
print(Solution().letterCombinations("2"))

1
2
3
4
5
6
7
8

# 2 解题思路

标签：回溯
首先使用哈希表存储每个数字对应的所有可能的字母，然后进行回溯操作。
回溯过程中维护一个字符串，表示已有的字母排列（如果未遍历完电话号码的所有数字，则已有的字母排列是不完整的）
该字符串初始为空。每次取电话号码的一位数字，从哈希表中获得该数字对应的所有可能的字母，并将其中的一个字母插入到已有的字母排列后面，然后继续处理电话号码的后一位数字，直到处理完电话号码中的所有数字，即得到一个完整的字母排列。
然后进行回退操作，遍历其余的字母排列。
回溯算法用于寻找所有的可行解，如果发现一个解不可行，则会舍弃不可行的解。在这道题中，由于每个数字对应的每个字母都可能进入字母组合，因此不存在不可行的解，直接穷举所有的解即可。

# 3 解题方法

from typing import List
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:return []
        a={'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(an,bn):
            if len(bn)==0:
                res.append(an)
            else:
                for x in a[bn[0]]:
                    backtrack(an+x,bn[1:])
        res=[]
        backtrack('',digits)
        return res

print(Solution().letterCombinations("23"))
print(Solution().letterCombinations(""))
print(Solution().letterCombinations("2"))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第1-3，17-19行： 题目中已经给出的信息，运行代码时要根据这些代码进行编辑
第4行： 当字符串是空字符串时，直接返回空列表即可
第5行： 创建哈希表a并为其中每个元素赋值
第7行： 创建backtrack回溯函数，内部变量分别为可能的组合以及需要求的原字符串
第8-9行： 当原字符串遍历完成时，在res列表中添加该可能组合
第10-11行： 未遍历完成时，使用for循环对哈希表a中字符串数字对应的字母进行遍历
第12行： 对该剩下的an、bn进行回溯
第13行： 创建空列表res用于存放组合
第14行： 使用backtrack函数进行操作
第15行： 返回最终的所有组合形成的列表

代码运行结果为：

# 算法讲解

这里用到了基础算法：回溯，简单讲解下这个算法：
回溯
回溯是很经典的一个算法，什么是回溯，回溯其实是一种暴力枚举的方式，为啥都暴力了还是很经典的一种方法呢，其实是因为有些问题我们能暴力出来就不错了，就别要其他自行车了。常见的回溯类问题：组合；排列；切割；子集；棋牌；
其实回溯算法就是常说的DFS,本质上是一种暴力枚举算法；
回溯算法常用于解决的问题：
组合
排列
切割
子集
棋盘：N皇后

比如最经典的排列。从1,2,3,4,5中取3个数组成排列有多少种，我们肯定会解决这种问题，但是程序怎么写呢。想一下我们解决这个问题的过程，我们先选1，然后第二个数可以选2，第三个数可以选3，这是一种答案了，然后呢，换第三个数，第三个数选4，又一种答案，再换，第三个数选5，没得选了，所以以12打头的数都选完了，得到三种答案.然后再换第二个数，第二个数选3，然后第三个数选4，注意是组合问题所以我们不能退往回选2了，不然就重复了。就是这样一种选择方案，一直到第3个数选成了3，得到答案345，就不用往后进行了。

# 4 视频解析

高清视频讲解，请查看AI大学堂Python基础实战100例 (opens new window)
关注『讯飞AI大学堂』公众号，发送 python100 即可领取Python基础实战100例源代码
AI大学堂公众号.png