Title: Letter Combinations of a Phone Number Source: leetcode.com
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.
image source: leetcode.com
|
1 2 |
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.
Python solution
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
''' https://leetcode.com/problems/letter-combinations-of-a-phone-number/ ''' class Solution(object): def __init__(self): s = {} s['1'], s['2'] = '*','abc' s['3'], s['4'] = 'def', 'ghi' s['5'], s['6'] = 'jkl', 'mno' s['7'], s['8'] = 'pqrs', 'tuv' s['9'], s['0'] = 'wxyz', ' ' self.d = s self.res = [] def helper(self, digits, s): if not digits: self.res.append(s) else: for c in self.d[digits[0]]: self.helper(digits[1:], s + c) def letterCombinations(self, digits): """ :type digits: str :rtype: List[str] """ if not digits: return self.res self.helper(digits, '') return self.res |