logo标签列表

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

pythonbacktracking
3

我正在为我的面试做准备。我正在解决的问题是如何获取电话号码的所有字母组合。

给定一个包含从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
如果你希望有一个更优雅的解决方案，这里提供一个：["".join(combo) for combo in itertools.product(*[letters[d] for d in digits])]。其中itertools.product函数用于返回所有可迭代对象中元素的笛卡尔积，使用列表推导式将每个数字对应的字母列表作为参数传递给product函数，然后再用join函数将组合成字符串。 - DYZ
谢谢，但那对面试不起作用。 - Dawn17
6个回答
2

我不明白你为什么要使用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:

此外，您还应该考虑@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']
1
让我们从伪代码的角度来看一下这个问题：

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)
0
L = {'2':"abc",'3':"def",'4':"ghi",'5':"jkl",
     '6':"mno",'7':"pqrs",'8':"tuv",'9':"wxyz"}
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            # always validate the input
            return []
        res=[]
        def dfs(i,cur):
            if len(cur)==len(digits):
                res.append(cur)
                return
            for letter in L[digits[i]]:
                dfs(i+1,cur+letter)
        dfs(0,"")
        return res

这是决策树示例：

enter image description here

在最坏的情况下，我们可能会得到“77”或“99”，这将导致有4个分支。因此，时间复杂度为 O((4^n)*n)。
0
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', ...
乍一看，这似乎不是递归的，所以可能有人没有仔细看就将其投票为负。但这是一个很好的答案+1。 - Primusa
哈哈，也许我应该更好地解释我的答案。谢谢！ - Osman Mamun
0
如果你想知道为什么你的代码不起作用，那是因为你在函数调用中包含了最后一位数字。这导致它与最后一位数字创建了不可能的配对。要解决这个问题，你只需要在除了最低级别之外的所有级别上少迭代一次数字，具体如下：
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
0
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        phoneKeypad = {'2':'abc', '3':'def','4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs','8':'tuv', '9':'wxyz'}
        if digits == "":
            return []
        numbers = list(phone_map[digits[0]])
        for digit in digits[1:]:
            numbers = [old+new for old in numbers for new in list(phoneKeypad[digit])]
        return numbers
这是很多代码，你能帮我们理解它是如何工作的吗？ - Simas Joneliunas
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接