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"].
input = "23"
0 [ ]
/ | \
1 [a] [b] [c]
/ | \ ........
2 [ad] [ae] [af]
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
if not digits:
return []
hashmap = {"2":"abc", "3":"def", "4":"ghi", "5":"jkl", "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
result =[]
self.dfs(digits, hashmap,0,"",result)
return result
def dfs(self, digits, hashmap, index, path, result):
if len(path) == len(digits):
result.append(path)
for i in xrange(index, len(digits)):
for j in hashmap[digits[i]]:
self.dfs(digits, hashmap, i+1,path+j,result)