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

Question

我目前正在练习我的面试。我正在研究的问题是获取电话号码的所有字母组合。给定一个包含 2-9 位数字的字符串，返回该数字可以表示的所有可能的字母组合。下面给出了数字到字母的映射（就像在电话按钮上一样）。请注意，1 不映射到任何字母。是问题所在，数字-字母对的映射如下所示：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 的超级简洁和令人敬畏的解决方案，它使用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']

Answer 2

让我们从伪代码中看一下：

if digits is empty

    path is a solution

else

    for each letter in current digit

        stick the letter on the front of

           the letter combos for the rest of the input

这给了我们更短的编程：

def backtrack(digits, path, res):

    if len(digits) == 0:

        res.append(path)

    else:

        for letter in letters[digits[0]]:

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

Answer 3

In [34]: def get_prod(number_list):

...:     let_list = [nums[i] for i in number_list]

...:     r = [[]]

...:     for p in let_list:

...:         r = [x + [y] for x in r for y in p]

...:     return [''.join(i) for i in r]

...:

...:

In [35]: get_prod(['2', '3', '4'])

Out[35]:

['adg',

 'adh',

 'adi',

 'aeg', ...