17. Letter Combinations of a Phone Number

2019-03-28

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:

1
2
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.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def letterCombinations(self, digits):
        # 创建字典
        mapping = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                   '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        # 没有数字输出空
        if len(digits) == 0:
            return []
        # 一个数字输出数字Value
        if len(digits) == 1:
            return list(mapping[digits[0]])
        # 多位数字
        # 前位数字（可能多位
        prev = self.letterCombinations(digits[:-1])
        # 后位数字，取digits[-1]
        additional = mapping[digits[-1]]
        return [s + c for s in prev for c in additional]
        #等价于
        #res=[]
        #for i in range(len(prev)):
        #    for j in range(len(additional)):
        #        res+=[prev[i]+additional[j]]
        #return res

多位时：先取最后一位，然后前边的重递归（取最后一位，然后前面递归），最后结果循环遍历

-->