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)
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]``````

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