Edfbf9215d66216e3d514596477b7abd
(难度Medium) Problem 17: Letter Combinations of a Phone Number

Problem 17: Letter Combinations of a Phone Number

链接

Letter Combinations of a Phone Number - LeetCode

难度等级

Medium

题干

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.

题意

题意很简单,给定一个我们常用的手机9键的字母盘,和一串数字的按键顺序,要求对应的按键能够组合成多少种字母组合。

样例

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

题解

这道题说是Medium难度,其实只有简单难度。

每个数字对应哪些字母这个是已经确定的,字母的顺序也有了。我们只需要一位一位地枚举数字,找到它对应的字母,然后把它加到已有的字母组合后面更新结果就行了。

比如,在没有数字的时候,答案就是一个空串“”。接着是第一个数字2,它对应abc三个字母,那么对应的结果就更新为:[“a”, “b”, “c”],接着是第二个数字3,它对应cde这三个字母,把它们分别下到之前的结果后面,可以得到:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf”],以此类推就可以得到最终答案。

很容易想到递归的解法:

def dfs(k, vec):
    if k >= n:
        return vec
    chs = mp[str[k]]
    cur = []
    for c in chs:
        for str in vec:
            cur.append(str+c)
    dfs(k+1, cur)
top Created with Sketch.