LeetCode Notes_#17 Letter Combinations of a Phone Number
Contents
题目
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.
illustration
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.
思路和解答
思路
-
题意
每一个数字代表几个字母，那么输入两个数字，就代表所有两个数字对应字母的组合。输入一串数字，要输出这串数字所代表的所有字母组合。 -
思路
解答
#看的答案...
class Solution:
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
mapping={'2':'abc','3':'def','4':'ghi','5':'jkl','6':'mno','7':'pqrs','8':'tuv','9':'wxyz'}
if len(digits)==0:
return []
if len(digits)==1:
return list(mapping[digits[0]])
prev=self.letterCombinations(digits[:-1])#除了最后一个数字的前面几个数字的字母组合
additional=mapping[digits[-1]]#最后一个数字里边的字母组成的字符串
return [s+c for s in prev for c in additional]
大概看懂他的意思了，简单的来梳理一下：
- 总体来说还是一个递归的思想，高维的问题转化为低维去解决，3个数字输入，转化为2（prev）+1(additional)，先找到前两个数字所代表的所有字母组合，然后跟最后一个数字的字母拼接起来即可
- 而2个数字的输入问题，又可以转化为1+1，而1+1的问题解决起来其实很容易，直接两轮循环，拼接字符串即可，那么就可以得到第一次的letterCombination的结果prev（#13）
- 然后继续运行最后一行，依然两轮循环，只不过其中的s已经是两个字母组合的结果了，所以最终就得到了三个字母的所有组合的list
- 递归真的不好看懂....这时候大不了可以开ide调试一下，一步一步知道代码在干什么就可以了