[leetcode]17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

 

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

Input: "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.

 

class Solution(object):
    def makeCombi(self, digits, prefix, numberdict,result ):
        if digits == "":
            result.append(''.join(prefix))
            return 
        
        charlist = numberdict[digits[0]]
        for c in charlist:
            prefix.append(c)
            self.makeCombi(digits[1:], prefix, numberdict, result)
            prefix.pop()
        return 
    
    def letterCombinations(self, digits):
        result = []
        
        if digits == "":
            return result
        
        numberdict ={'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.makeCombi(digits,[],numberdict,result)
        return result

 

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