python 为什么下面的代码不能解决字母组合问题?

1zmg4dgp  于 2024-01-05  发布在  Python
关注(0)|答案(3)|浏览(146)
  1. def letterCombinations(digits: str) -> List[str]:
  2. result = []
  3. check_dict = {'2': ['a', 'b', 'c'],
  4. '3': ['d', 'e', 'f'],
  5. '4': ['g', 'h', 'i'],
  6. '5': ['j', 'k', 'l'],
  7. '6': ['m', 'n', 'o'],
  8. '7': ['p', 'q', 'r', 's'],
  9. '8': ['t', 'u', 'v'],
  10. '9': ['w', 'x', 'y', 'z']}
  11. if len(digits) == 0:
  12. return []
  13. elif len(digits) == 1:
  14. return check_dict.get(digits)
  15. else:
  16. digits1 = list(digits)
  17. dec_dict = {}
  18. for i in digits1:
  19. value = check_dict.get(i)
  20. dec_dict[i] = value
  21. to_do_value = list(dec_dict.values())
  22. for i in to_do_value[0]:
  23. for j in to_do_value[1:]:
  24. for k in j:
  25. z = i + k
  26. result.append(z)
  27. return result

字符串
问题是Leetcode Q17:17. Letter Combinations of a Phone Number。大多数测试用例都通过了,但是如果输入像'22''99',代码输出[]。我的代码有什么问题?

edqdpe6u

edqdpe6u1#

在此Forge代码片段中,

  1. digits1 = list(digits)
  2. dec_dict = {}
  3. for i in digits1:
  4. value = check_dict.get(i)
  5. dec_dict[i] = value

字符串
当你创建数字1时,它看起来像这样(例如:'22')

  1. ['2', '2']


所以 * 在dec_dict的第一次迭代中,添加了一个值为“2”的键 *,所以当你试图在第二次迭代中添加另一个“2”时,字典只是使用该迭代的新值,而不是创建一个新值,因为字典中不能存在两个相同的键
所以在这个循环结束后,dec_dict看起来像这样

  1. {'2': ['a', 'b', 'c']}


现在来看这个片段

  1. to_do_value = list(dec_dict.values())
  2. for i in to_do_value[0]:
  3. for j in to_do_value[1:]:
  4. for k in j:
  5. z = i + k
  6. result.append(z)


todo_values变为等于['a ',' b','c']],并且todo_values[1:]不存在。因此,循环不会运行,不会向结果追加任何内容,结果保持为空

展开查看全部
rvpgvaaj

rvpgvaaj2#

据我所知,当有两个以上的数字或相同的数字重复时,您的代码不能正确地混合字母。
它只将第一组字母与其他字母组合在一起,但不会尝试所有不同的混合方式。当你有“22”或“99”这样的数字时,你的代码根本不会进行任何混合。

r6hnlfcb

r6hnlfcb3#

你可以使用一个递归函数('backtrack')。

  1. from typing import List
  2. class Solution:
  3. def letterCombinations(self, digits: str) -> List[str]:
  4. def backtrack(combination, next_digits):
  5. if not next_digits:
  6. result.append(combination)
  7. return
  8. for letter in check_dict[next_digits[0]]:
  9. backtrack(combination + letter, next_digits[1:])
  10. result = []
  11. check_dict = {
  12. '2': ['a', 'b', 'c'],
  13. '3': ['d', 'e', 'f'],
  14. '4': ['g', 'h', 'i'],
  15. '5': ['j', 'k', 'l'],
  16. '6': ['m', 'n', 'o'],
  17. '7': ['p', 'q', 'r', 's'],
  18. '8': ['t', 'u', 'v'],
  19. '9': ['w', 'x', 'y', 'z']
  20. }
  21. if digits:
  22. backtrack('', digits)
  23. return result

字符串

展开查看全部

相关问题