本文讲述了python基础编程100例：第79期-基础算法：回溯 电话号码的字母组合！具有很好的参考价值，希望对大家有所帮助。一起跟随六星小编过来看看吧，具体如下:

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

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"))

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-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，就不用往后进行了。

更多相关技术内容咨询欢迎前往并持续关注六星社区了解详情。

想高效系统的学习Python编程语言，推荐大家关注一个微信公众号：Python编程学习圈。每天分享行业资讯、技术干货供大家阅读，关注即可免费领取整套Python入门到进阶的学习资料以及教程，感兴趣的小伙伴赶紧行动起来吧。