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 = {

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 == '':
        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


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