每天一道算法题：17. 电话号码的字母组合

组合"/>

每天一道算法题：17. 电话号码的字母组合

难度

中等

题目

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

思路

从题意知道所有的字母组合，就是组合问题。
**组合 **是指从一组元素中选择若干个元素，不考虑元素的顺序，而只考虑元素的组合方式。组合通常用于解决从给定集合中选择子集的问题。
组合数 指的是不考虑元素顺序的情况下，从元素集合中选择指定数量的元素的方式的总数。
从 [2,3,4,5,6,7,8,9] 中选择2、3 键上对应的字母进行组合。
2 键上对应的字母为 a b c
3 键上对应的字母为 d e f
第一层选择 2 键上的 a ,第二层可以分别选择 3 键上的 d e f
第一层选择 2 键上的 b ,第二层可以分别选择 3 键上的 d e f
第一层选择 2 键上的 c ,第二层可以分别选择 3 键上的 d e f

代码

from typing import List
class Solution:mapping = {'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]:self.digits = digitsself.length = len(self.digits)self.result = []self.backtrack(0, [])print(self.result)return self.resultdef backtrack(self, h, tmp):# h 表示要递归的层数 也就是最多达到 digits的长度# tmp 记录值的栈# 终止条件，就是当递归的次数达到 digits的长度时结束if h == self.length:self.result.append(''.join(tmp[:]))return# 遍历之前先找出 数字所代表的所有字母# self.digits[h] h从0开始 表示digits中第h个元素chars = self.mapping[self.digits[h]]# 因为每一层要遍历的元素都不一样，所以都需要从0位置开始，进行组合for i in range(len(chars)):tmp.append(chars[i])# 每层每次只添加一个元素 添加完后去下一层进行添加self.backtrack(h + 1, tmp)tmp.pop()if __name__ == '__main__':digits = "23"digits = "2"s = Solution()s.letterCombinations(digits)