Letter Combinations of a Phone Number-蒲公英云

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.

200px-Telephone-keypad2.svg.png

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

这题是组合题，思路很简答，需要同时掌握迭代和递归两种方法。递归都很清楚，思路为dfs + backtracking,迭代版的思路为在之前生成的中间结果上再加一位构成现在的结果。

迭代版思路如下：

def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        hash = {
    '2':'abc', '3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
        #iterative method
        if not digits:
            return []
        res = [[]]
        for i in digits:
            tmp = []
            for j in hash[i]:
                for num in res:
                    tmp.append(num + [j]) ＃取之前结果加1位
            res = tmp + []
        return map(lambda x: ''.join(x),res)

递归版本：

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