6/24/2017 - 11:14 AM

17. Letter Combinations of a Phone Number

  1. Letter Combinations of a Phone Number
class Solution(object):
    def letterCombinations(self, digits):
        :type digits: str
        :rtype: List[str]
        self.numDict = {'0':[' '], '1':['*'], '2':['a', 'b', 'c'], '3':['d', 'e', 'f'], \
                        '4':['g', 'h', 'i'], '5':['j', 'k', 'l'], '6':['m', 'n', 'o'], \
                        '7':['p', 'q', 'r', 's'], '8':['t', 'u', 'v'], '9':['w', 'x', 'y', 'z']}
        self.res = []
        self.cur = []
        if len(digits) == 0:
            return self.res
        self.backtracking(digits, 0)
        return self.res
    def backtracking(self, digits, start):
        if len(digits)-1 < start :
            resStr = reduce(lambda x,y:x+y, self.cur)
        for eachL in self.numDict[digits[start]]:
            self.backtracking(digits, start+1)
            del self.cur[-1]

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"].