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

1zmg4dgp  于 5个月前  发布在  Python
关注(0)|答案(3)|浏览(49)
def letterCombinations(digits: str) -> List[str]:
    result = []
    check_dict = {'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']}

    if len(digits) == 0:
        return []
    elif len(digits) == 1:
        return check_dict.get(digits)
    else:
        digits1 = list(digits)
        dec_dict = {}
                
        for i in digits1:
            value = check_dict.get(i)
            dec_dict[i] = value
    
        to_do_value = list(dec_dict.values())
        for i in to_do_value[0]:
            for j in to_do_value[1:]:
                for k in j:
                    z = i + k
                    result.append(z)

    return result

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

edqdpe6u

edqdpe6u1#

在此Forge代码片段中,

digits1 = list(digits)
    dec_dict = {}
            
    for i in digits1:
        value = check_dict.get(i)
        dec_dict[i] = value

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

['2', '2']


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

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


现在来看这个片段

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


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

rvpgvaaj

rvpgvaaj2#

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

r6hnlfcb

r6hnlfcb3#

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

from typing import List

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        def backtrack(combination, next_digits):
            if not next_digits:
                result.append(combination)
                return
            for letter in check_dict[next_digits[0]]:
                backtrack(combination + letter, next_digits[1:])

        result = []
        check_dict = {
            '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']
        }

        if digits:
            backtrack('', digits)
        
        return result

字符串

相关问题