网站开发google,嵌入式开发培训班费用大概多少,运城手机网站制作,柚段子wordpress文章本文目录 1 中文题目2 最优解法#xff1a;迭代法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下#xff08;与电话按键相… 本文目录 1 中文题目2 最优解法迭代法2.1 方法思路2.2 Python代码2.3 复杂度分析 3 题目总结 1 中文题目
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。
示例
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]输入digits
输出[]输入digits 2
输出[a,b,c]提示 0 ≤ d i g i t s . l e n g t h ≤ 4 0 \leq digits.length \leq 4 0≤digits.length≤4 2 ≤ d i g i t s [ i ] ≤ 9 2 \leq digits[i] \leq 9 2≤digits[i]≤9 2 最优解法迭代法
2.1 方法思路
方法核心
每处理一个数字就将当前所有可能的组合与这个数字对应的字母进行组合得到新的所有可能组合。
实现步骤
初始化一个只包含空字符串的结果列表 result []遍历输入的每个数字对于每个数字 获取该数字对应的所有可能字母将已有的每个组合与当前数字的每个字母进行拼接形成新的组合
方法示例
以输入23为例说明过程
处理’2’时result [] → [‘a’, ‘b’, ‘c’]处理’3’时[‘a’, ‘b’, ‘c’] → [‘ad’, ‘ae’, ‘af’, ‘bd’, ‘be’, ‘bf’, ‘cd’, ‘ce’, ‘cf’]
2.2 Python代码
class Solution:def letterCombinations(self, digits: str) - List[str]:# 处理空输入if not digits:return []# 数字到字母的映射字典digit_map {2: abc,3: def,4: ghi,5: jkl,6: mno,7: pqrs,8: tuv,9: wxyz}# 存储结果result []# 遍历每个数字for digit in digits:# 临时列表存储新的组合new_result []# 获取当前数字对应的字母letters digit_map[digit]# 遍历现有的组合for combo in result:# 将当前数字对应的每个字母添加到现有组合中for letter in letters:new_result.append(combo letter)# 更新结果列表result new_resultreturn result2.3 复杂度分析
时间复杂度 O ( 4 n ) O(4^n) O(4n) n n n是输入数字的长度 每个数字最多对应 4 4 4个字母每次迭代产生的组合数呈指数增长 空间复杂度 O ( 4 n ) O(4^n) O(4n) 需要存储所有可能的组合空间占用主要在结果列表 3 题目总结
题目难度中等 数据结构数组 应用算法迭代法
