class Solution(object):

    def letterCombinations(self, digits):

        """

        :type digits: str

        :rtype: List[str]

        """

        if len(digits) <= 0:

            return list()

        alpha = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]

        res=[]

        word=[]

        def dfs(cur):

            if cur >= len(digits):

                res.append(''.join(word))

            else:

                for x in alpha[int(digits[cur])-(int)('')]:

                    word.append(x)

                    dfs(cur+1)

                    word.pop()

        dfs(0)

        return res