moonlightshadow123
6/24/2017 - 11:14 AM

17. Letter Combinations of a Phone Number

  1. Letter Combinations of a Phone Number
solution.py
content_copyfile_download
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)
            self.res.append(resStr)
            return
        for eachL in self.numDict[digits[start]]:
            self.cur.append(eachL)
            self.backtracking(digits, start+1)
            del self.cur[-1]
17-Letter-Combinations-of-a-Phone-Number.md
content_copyfile_download
  • Rendered
  • Source

https://leetcode.com/problems/letter-combinations-of-a-phone-number/#/description

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