python - 回溯获取电话号码的所有字母组合

Question

我目前正在为面试练习。我正在研究的问题是获取电话号码的所有字母组合。

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

是问题所在，数字字母对的映射如下所示:

nums = {
    '2':'abc',
    '3':'def',
    '4':'ghi',
    '5':'jkl',
    '6':'mno',
    '7':'pqrs',
    '8':'tuv',
    '9':'wxyz'
}

我对这个问题的解决方案如下:

def letterCombinations(self, digits):
    """
    :type digits: str
    :rtype: List[str]
    """

    letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}

    def backtrack(digits, path, res):
        if digits == '':
            res.append(path)
            return
        for n in digits:
            for letter in letters[n]:
                path += letter
                backtrack(digits[1:], path, res)
                path = path[:-1]


    res = []
    backtrack(digits, '', res)
    return res

输入 "23" 的正确答案应该是 ["ad","ae","af","bd","be","bf","cd","ce","cf"] 但是，我的答案看起来像

["ad","ae","af","bd","be","bf","cd","ce","cf","dd","de","df","ed","ee","ef","fd","fe","ff"]

在它得到所有想要的组合后，它会不断得到那些有重叠字母的组合，比如 dd de ee 等。

我不明白为什么会这样，因为我只是尝试遍历每个数字的可能字母并在之后终止。

是什么导致这里的错误？

Answer 1

我不明白你为什么要for n in digits:，每次回溯时你应该只关注当前数字 (digits[0])，遍历该数字的所有可能值，然后将其余工作传递给下一个递归调用。删除该行并将 n 更改为 digits[0] 可解决您的问题:

def letterCombinations(digits):
    """
    :type digits: str
    :rtype: List[str]
    """

    letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}

    def backtrack(digits, path, res):
        if digits == '':
            res.append(path)
            return
        for letter in letters[digits[0]]:

            # note that you can replace this section with 
            # backtrack(digits[1:], path + letter, res)

            path += letter
            backtrack(digits[1:], path, res)
            path = path[:-1]


    res = []
    backtrack(digits, '', res)
    return res

letterCombinations('23')

输出:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']

另外你应该考虑@DYZ 的 super 简洁和很棒的解决方案，它使用 itertools:

import itertools
letters = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}

def letterCombinations(digits):
    return ["".join(combo) for combo in itertools.product(*[letters[d] for d in digits])]

print(letterCombinations('23'))

输出:

['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']