[LeetCode]题解（python）：017-Letter Combinations of a Phone Number

题目来源：

https://leetcode.com/problems/letter-combinations-of-a-phone-number/

题意分析：

这道题是输入一段数字字符digits，在手机上每个数字所对应不同的字符。具体对应如图：

返回所有的数字字符对应的字符的可能。比如输入“123”，那么输出["*ad","*ae","*af","*bd","*be","*bf","*cd","*ce","cf"].

题目思路：

看到这道题目让我想起了向量的笛卡尔乘积。这道题目可以用类似DP的方法去解决。dp[n] = dp[n -1]X最后一个字符对应的字符串，其中"X"代表内积，也就是说f("123") = f("1") X f("2") X f("3").首先建立一个字典，d = {'0':' ','1':'*','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}；然后对利用笛卡尔乘积做法得到答案。

代码（python）：

 1 class Solution(object):
 2     def addDigit(self,digit,ans):
 3         tmp = []
 4         for element in digit:
 5             if len(ans) == 0:
 6                 tmp.append(element)
 7             for s in ans:
 8                 tmp.append(s + element)
 9         return tmp
10     def letterCombinations(self, digits):
11         """
12         :type digits: str
13         :rtype: List[str]
14         """
15         ans = []
16         d = {'0':' ','1':'*','2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
17         for element in digits:
18             ans = self.addDigit(d[element],ans)
19         return ans

View Code

转载请注明出处：http://www.cnblogs.com/chruny/p/4835631.html