Letter Combinations of a Phone Number

拼搏现实的明天。 2021-12-17 10:41 194阅读 0赞

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()

总结而言python处理这种题不是很高效，主要在于string类型对象不可以修改。

转载于:https://www.cnblogs.com/sherylwang/p/5764002.html

[200px-Telephone-keypad2.svg.png]: /images/20211217/afef18af25bc455dbdd7d96ca0bd00f9.png