Given a digit string, return all possible letter combinations that the number could represent.

Input: Digit string "23"

Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

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