class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if not digits:
            return []
        dic = {‘2‘:‘abc‘,‘3‘:‘def‘,‘4‘:‘ghi‘,‘5‘:‘jkl‘,‘6‘:‘mno‘,‘7‘:‘pqrs‘,‘8‘:‘tuv‘,‘9‘:‘wxyz‘}
        result = []
        self.helper(digits,dic,0,"",result)
        return result
    
    def helper(self,digits,dic,index,temp,result):
        if index==len(digits):
            result.append(temp)
        else:
            s = dic[digits[index]]
            for i in s:
                temp += i
                self.helper(digits,dic,index+1,temp,result)
                temp = temp[:-1]