LeetCode17电话号码的字母组合

发表于 | 更新于 | 分类于 |

题目描述：

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例:

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

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

解答思路：

读完题目之后，基本就能感觉出来这题需要使用回溯方法来做。

回溯方法的关键就是找到回溯循环和临界条件。

以数字23为例，来理解这个问题：

需要回溯的循环就是 每一层都循环遍历所表示的字符，然后外层需要遍历完所有的数字

临界条件就是层数指针高于最大层数。

代码实现：

使用Python3实现的code，GitHub地址为：https://github.com/zhangdianlei/LeetCode_python/blob/master/src/c17.py

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
27

def back(digits, str, index, result):
    chars = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    if len(digits) == index:
        result.append(str)
        return

    for item in chars[int(digits[index])]:
        back(digits, str+item, index + 1, result)


class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        str = ""
        result = []
        index = 0

        if len(digits) == 0:
            return result

        back(digits, str, index, result)

        return result