Leetcode 78子集

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
>输入：digits = "23"
>输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
>输入：digits = ""
>输出：[]

示例 3：

1
2
>输入：digits = "2"
>输出：["a","b","c"]

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
        n = len(digits)
        if n == 0:
            return []

        ans = []
        path = [''] * n

        def dfs(i):
            # 当遍历到最后一位的时候退出
            if i == n:
                ans.append(''.join(path))
                print(ans)
                return
            # 从字典找取出下一位的字符，然后逐个遍历进入
            for c in MAPPING[int(digits[i])]:
                path[i] = c
                dfs(i + 1)
        dfs(0)
        return ans