本文主要是介绍回溯——3.电话号码的字母组合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣题目链接
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
- 输入:"23"
- 输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解题思路总结:
- 映射表建立: 通过
letterMap
将数字0-9与对应的字母集合关联起来。 - 递归生成组合: 使用递归来遍历所有可能的字母组合,递归的每一层处理一个数字,逐层向组合字符串添加对应的字母。
- 终止条件: 当处理完所有数字时,保存生成的组合。
- 返回结果: 最终将所有可能的组合结果存储在
result
列表中并返回。
完整代码如下:
class Solution:def __init__(self):self.letterMap = ["", # 0"", # 1"abc", # 2"def", # 3"ghi", # 4"jkl", # 5"mno", # 6"pqrs", # 7"tuv", # 8"wxyz" # 9]self.result = []def getCombinations(self, digits, index, s):if index == len(digits):self.result.append(s)returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:self.getCombinations(digits, index + 1, s + letter)def letterCombinations(self, digits):if len(digits) == 0:return self.resultself.getCombinations(digits, 0, "")return self.result
def __init__(self):self.letterMap = ["", # 0"", # 1"abc", # 2"def", # 3"ghi", # 4"jkl", # 5"mno", # 6"pqrs", # 7"tuv", # 8"wxyz" # 9]self.result = []
letterMap
: 这是一个列表,保存了数字0到9分别对应的字母组合。手机键盘上,每个数字对应若干个字母,例如2对应abc
,3对应def
,等等。数字0和1没有对应的字母,所以列表的前两个元素是空字符串。result
: 这是一个列表,用于保存所有可能的字母组合。
def getCombinations(self, digits, index, s):if index == len(digits):self.result.append(s)returndigit = int(digits[index])letters = self.letterMap[digit]for letter in letters:self.getCombinations(digits, index + 1, s + letter)
-
- 递归终止条件:如果
index
等于digits
的长度,说明已经生成了一个完整的字母组合,将其加入result
列表,并返回。 - 递归过程:根据当前索引对应的数字,从
letterMap
中取出对应的字母集合,然后逐一将这些字母添加到当前字符串s
后面,递归调用getCombinations
处理下一个索引。
- 递归终止条件:如果
-
递归循环:
- 对于每一个可能的字母(通过
letters
获得),进行递归调用,同时索引加1,并将当前字母加入组合字符串s
。
- 对于每一个可能的字母(通过
def letterCombinations(self, digits):if len(digits) == 0:return self.resultself.getCombinations(digits, 0, "")return self.result
- 首先判断输入字符串
digits
是否为空,如果为空,直接返回result
(此时是一个空列表)。 - 如果不为空,调用
getCombinations
方法,从索引0开始递归生成组合,最后返回所有可能的字母组合result
。
这篇关于回溯——3.电话号码的字母组合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!