Leetcode 17 Letter Combinations of a Phone Number

发表于 |

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
2: abc
3: def
4: ghi
5: jkl
6: mno
7: pqrs
8: tuv
9: wxyz

示例：
输入：”23”
输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

题意分析：
相当于求一个全排列问题

思路分析：
这道题是在考你迭代用得怎么样
我们来看几种情况：

  1. 假设只有一个数字2： 那么返回 ‘a’,’b’,’c’
  2. 两个数字23: 在第一种的情况下每个都分别加上’d’,’e’,’f’，返回[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
  3. 三个数字234:在第二种的情况下每个都分别加上’g’,’h’,’i’

明白这个规律这道题就可以做了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 20ms, beats 100%
class Solution(object):
    def letterCombinations(self, digit):
        if not digit: return []
        
        d = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
        res = ['']
        rec = []
        for num in digit:
            for ss in d[num]:
                for s in res:
                    rec.append(s + ss)
            res = rec
            rec = []
        return res