Letter Combinations of a Phone Number

Question

Given a digit string, 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.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note: Although the above answer is in lexicographical order, your answer could be in any order you want.

Tags

• Backtracking
• String

Thought

Use backtracking here.

Code

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        myDict = {}
        myDict[2] = ['a', 'b', 'c']
        for i in xrange(3, 7):
            myDict[i] = []
            for ch in myDict[i - 1]:
                myDict[i].append(chr(ord(ch) + 3))
        myDict[7] = list('pqrs')
        myDict[8] = list('tuv')
        myDict[9] = ['w', 'x', 'y', 'z']
        result = []

        def helper(current, digits):
            if digits == '':
                if current != '':
                    result.append(current)
                return
            digit = int(digits[0])
            for ch in myDict[digit]:
                helper(current + ch, digits[1:])

        helper('', digits)
        return result