Letter Combinations of a Phone Number

Given a digit string, 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.

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

input = "23"

    0               [ ]
               /     |     \
    1      [a]      [b]    [c]
         / |  \      ........
    2 [ad] [ae] [af]

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

这题的时间复杂度是O(3^n) (exponential)每个数字对应的有3个字母，所有 n 个数字就有 3^n 个答案，每个答案就是O(1)