【算法 -- LeetCode】（17） 电话号码的字母组合

**算法 -- LeetCode**

**(17)电话号码的字母组合**

**问题描述**

给定一个仅包含数字的字符串 `digits` 和一个空字符串 `combination`，请你找出所有可能的字母组合并将它们添加到 `combination` 中。

每个数字对应于4 种字母（0-9），但0 不可以作为首位数字。例如，如果输入 `"23"`, 则输出应该是 `"adg", "aei", "afy", "bdg", "bei", "bfy", "cdg", "cei", "cfy"`。

**示例**

* 输入：`digits = "23"`
输出：`["adg","aei","afy","bdg","bei","bfy","cdg","cei","cfy"]`
* 输入：`digits = ""`
输出：`[]`

**解决方案**

我们可以使用回溯法来解决这个问题。回溯法是一种用于求解满足某些条件的所有可能解的算法。

首先，我们需要定义一个函数 `backtrack` 来生成所有可能的字母组合。这个函数将接受当前的数字和当前的组合作为参数。

def backtrack(combination, next_digits):
 # 如果没有更多的数字，则添加到结果中 if len(next_digits) ==0:
 result.append(combination)
 else:
 # 获取下一个数字对应的字母 letter = phone_map[next_digits[0]]
 # 遍历每个字母 for l in letter:
 # 添加到当前组合中并递归调用backtrack函数 backtrack(combination + l, next_digits[1:])

def letterCombinations(digits):
 # 如果输入为空，则返回空列表 if not digits:
 return []
 # 初始化结果列表和电话映射表 result = []
 phone_map = {
 "2": "abc",
 "3": "def",
 "4": "ghi",
 "5": "jkl",
 "6": "mno",
 "7": "pqrs",
 "8": "tuv",
 "9": "wxyz"
 }
 # 添加首位数字对应的字母 backtrack("", digits)
 return result

print(letterCombinations("23")) # ["adg","aei","afy","bdg","bei","bfy","cdg","cei","cfy"]
print(letterCombinations("")) # []