代码之家 › 专栏 › 技术社区 › Dawn17

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

backtracking python

Dawn17 · 技术社区 · 7 年前

我目前正在练习面试。我正在研究的问题是如何获得一个电话号码的所有字母组合。

给定一个包含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 等。

我不明白为什么会发生这种情况,因为我只试着检查每个数字可能的字母,然后在那之后结束。

是什么引起了这个问题?

4 回复 | 直到 7 年前

Primusa 7 年前

我不明白你为什么这么做 for n in digits: ,每次回溯时,您应该只注意当前数字。( digits[0] ,遍历该数字的所有可能值,然后将其余工作传递给下一个递归调用。在更换的同时拆下那根线 n 到 数字〔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']

Prune 7 年前

让我们从伪代码中看一看:

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)

Osman Mamun 7 年前

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', ...

Recessive 7 年前

如果您想知道为什么您的代码不能工作,那是因为您在函数调用中包含了最后一个数字。这导致它无法与最后一个数字配对。要解决这个问题,您只需在除最低级别之外的所有级别的数字上重复一次,如下所示:

def a(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
        if len(digits) == 1:
            for letter in letters[digits[0]]:
                path += letter
                backtrack(digits[1:], path, res)
                path = path[:-1]
        else:
            for n in range(len(digits)-1):
                for letter in letters[digits[n]]:
                    path += letter
                    backtrack(digits[1:], path, res)
                    path = path[:-1]

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