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”].

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

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

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

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


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

leetcode 17 letter combinations of a phone number

近期文章

近期评论

标签

热门

文章归档

分类目录

功能