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

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 resletterCombinations('23')输出：['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']此外，您应该考虑@DYZ 的超级简洁和令人敬畏的解决方案，它使用itertools：import itertoolsletters = {'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 solutionelse    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', ...