字母组合的一个电话号码太多组合在输出？
我正在研究Leetcode 17:电话号码的字母组合，但是我的第一次尝试在输出中产生了太多的组合。
如果字符串包含来自2-9的数字，则返回数字可以表示的所有可能的字母组合。返回any order中的答案。下面给出了数字到字母的映射(就像在电话按钮上一样)。请注意，1不映射到任何字母。
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'
}
combinations = []
def generate_combinations(combination, digits):
if not digits:
combinations.append(combination)
return
for digit in digits:
for ch in digit_map[digit]:
generate_combinations(combination+ch, digits[1:])
generate_combinations('', digits)
return combinations输入"234“将得到输出["ad","ae","af","bd","be","bf","cd","ce","cf","dd","de","df","ed","ee","ef","fd","fe","ff"]。我试图为上面的解决方案绘制递归树。
。我修改了我的代码，以便只考虑到下面代码的第一个数字(以数字表示)。
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'
}
combinations = []
def generate_combinations(combination, digits):
if not digits:
combinations.append(combination)
return
digit = digits[0]
for ch in digit_map[digit]:
generate_combinations(combination+ch, digits[1:])
generate_combinations('', digits)
return combinations给出了正确的解决方案。再一次，我尝试绘制递归树。
。第一个解决方案是错误的，因为一旦使用了来自输入的数字，就不应该再使用它了吗？此外，我还试图分析时间和空间的复杂性，以找到正确的解决方案。设N =len(数字)。
- 时间复杂度：
O(N*4^N)。树的分支因子是4，b/c，一些数字如7和9映射到四个不同的字母(7->pqrs)和(9->wxyz)。然后，因为字符串在python中是不可变的，所以它是一个O(N)操作，用于创建combination的副本并将其传递给每个递归调用。这棵树有N的高度。 - 空间复杂性：
O(N)
有人能告诉我我的复杂性分析是否正确吗？
回答 2
Stack Overflow用户
发布于 2022-07-31 02:19:16
第一个解决方案有点错误，因为它只为一个3个字符的输入生成两个字符的字符串，而问题则定义了一个n字符输入的正确输出是一个n字符字符串的列表。这是因为您选择在每个递归调用中迭代完整的剩余输入字符串，这是以导致截断最后一个数字的方式实现的：
for digit in digits:
for ch in digit_map[digit]: 这是不必要的，因为在每个递归操作中，您只需要处理一个字符--输入字符串中的下一个字符，而不是所有字符。
关于复杂性分析，解决此问题的最佳运行时复杂性是O(4^N)，因为您正在生成O(4^N)项，它本质上至少需要O(4^N)操作。你对你的解决方案的分析似乎是正确的。考虑如何进一步降低运行时复杂性可能是一个有趣的挑战，但是解决其他问题可能是更好地利用您的时间和精力。
Stack Overflow用户
发布于 2022-08-14 01:23:58
以"23“为例，这是我们希望达到的目标：
- 2被映射到"abc“。
- 3被映射为"def“。
- 我们需要从"abc“中的每个字母映射到"def”中的每个字母。 阿德阿夫 be bf cf
对于"abc“中的每一个字母，我们必须写一个for循环。
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'
}
combinations = []
def generate_combinations(combination,position):
if position==len(digits):
combinations.append(combination)
return
for ch in digit_map[digits[position]]:
generate_combinations(combination+ch, position+1)
generate_combinations('', 0)
return combinations您将把backtrack("",0)推到调用堆栈中。在第一个for-循环中，它将添加"a“，然后调用backtrack("a",1)。现在在backtrack("a",1)函数中，它将为"def“运行for -循环，并将"def”中的每个字母运行到"a“，因此您将创建"ad af”。在完成这个for循环之后，它将对"b“和"c”执行相同的操作。
https://stackoverflow.com/questions/73180147
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号