leetcode17

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

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        self.dic = {
            '2':"abc",
            '3':'def',
            '4':'ghi',
            '5':'jkl',
            '6':'mno',
            '7':'pqrs',
            '8':'tuv',
            '9':'wxyz'
        }
        
        # digits = "".join(list(set(digits)))
        temp = self.helper(digits)
        ret = []
        for x in temp:
            if len(x)==len(digits):
                ret.append(x)
        return ret
    
    def helper(self, digits):
        res = []    
        # if len(digits)==0:
            # return []
        if len(digits)==1:
            return [x for x in self.dic[digits]]
        
        for i in range(len(digits)):
            temp = self.helper(digits[i+1:])
        
            for z in self.dic[digits[i]]:
                for y in temp:
                    res.append(z+y)
             
        return res