2
votes

Retour en arrière pour obtenir toutes les combinaisons de lettres d'un numéro de téléphone

Je m'entraîne actuellement pour mon entretien. La question sur laquelle je travaille est d'obtenir toutes les combinaisons de lettres d'un numéro de téléphone.

Étant donné une chaîne contenant des chiffres de 2 à 9 inclus, renvoie toutes les combinaisons de lettres possibles que le nombre pourrait représenter. Une correspondance entre les chiffres et les lettres (comme sur les touches du téléphone) est donnée ci-dessous. Notez que 1 ne correspond à aucune lettre.

C'est le problème, et la carte pour la paire chiffre-lettre ressemble à:

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

Ma solution à ce problème ressemble à:

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

La bonne réponse pour l'entrée "23" est censée être ["ad", "ae", "af", "bd" , "be", "bf", "cd", "ce", "cf"] Cependant, ma réponse ressemble à

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

Après avoir obtenu toutes les combinaisons souhaitées, il continue à obtenir celles dont les lettres se chevauchent comme dd de ee , etc.

Je ne comprends pas pourquoi cela se produit parce que j'essaie seulement de parcourir les lettres possibles pour chaque chiffre et de terminer après cela.

Qu'est-ce qui cause le bogue ici?

python backtracking

2 commentaires

Si vous souhaitez une solution plus élégante, la voici: ["" .join (combo) for combo in itertools.product (* [lettres [d] pour d en chiffres])]

Merci, mais cela ne fonctionnera pas pour les interviews.

4 Réponses :

2
votes

Je ne comprends pas pourquoi vous faites pour n chiffres: , chaque fois que vous revenez en arrière, vous ne devriez faire attention qu'au chiffre actuel ( chiffres [0] code>), en passant par toutes les valeurs possibles pour ce chiffre, puis en passant le reste du travail au prochain appel récursif. La suppression de cette ligne et le changement de n en chiffres [0] résout votre problème:

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

  Résultat: 
 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'))
  De plus, vous devriez considérer la solution super concise et géniale de @ DYZ qui utilise itertools:
['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
  Résultat:  p > 
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')

0 commentaires

0
votes

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

2 commentaires

À première vue, cela ne semble pas récursif, alors peut-être que quelqu'un a voté à la baisse sans trop regarder. Mais c'est une excellente réponse + 1.

Haha, j'aurais peut-être dû mieux expliquer ma réponse. Merci!

1
votes

Jetons un œil à ceci à partir du pseudo-code:

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)

Cela nous donne une programmation plus courte:

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

0 commentaires

0
votes

Si vous vous demandiez pourquoi votre code ne fonctionnait pas, c'est que vous incluiez le dernier chiffre dans votre appel de fonction. Cela l'a amené à créer des appariements impossibles avec le chiffre final. Pour résoudre ce problème, il vous suffit de parcourir une fois de moins les chiffres à tous les niveaux sauf le plus bas, comme suit:

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 commentaires