17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

解题要点：

用Backtracking的方法，反正就很巧妙。

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        res = []
        if len(digits) == 0:
            return res
        temp = ""
        key = {1:"",2:"abc",3:"def",4:"ghi",5:"jkl",6:"mno",7:"pqrs",8:"tuv",9:"wxyz"}
        
        def combinations(res, temp):
            if len(temp) == len(digits):
                res.append(copy.deepcopy(temp))
                return
            for i in key[int(digits[len(temp)])]:
                temp = temp + i
                combinations(res, temp)
                temp = temp[:-1]
            
        combinations(res, temp)
        return res