Linked Questions

Popular Questions

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?

Related Questions