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