Backtracking to get all Letter Combinations of a Phone Number

Question

I am currently practicing for my interview. The question that I am working on is getting all Letter Combinations of a Phone Number.

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Is the problem, and the map for the digit-letter pair looks like:

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

My solution to this problem looks like:

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

The correct answer for the input "23" is supposed to be ["ad","ae","af","bd","be","bf","cd","ce","cf"] However, my answer looks like

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

After it gets all the desired combination, it keeps getting the ones with overlapped letters like dd de ee, etc.

I don't get why this is happening because I only try to go through the possible letters for each digit and terminate after that.

What's causing the bug here?

Answer 1

Let's take a look at this from pseudo-code:

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

This gives us shorter programming:

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 2

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

Answer 3

If you were wondering as to why your code wasn't working, it was because you were including the last digit in your function call. This caused it to create impossible pairings with the final digit. To fix this, you just had to iterate one less time over the digits on all levels except the lowest , as follows:

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

Answer 4

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

this is the decision tree sample:

In worst-case scenario we would have "77" or "99" that would lead to have 4 branches. So time complexity is O((4^n)*n).