17_电话号码的字母组合
【问题描述】
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按任意顺序返回。给出数字到字母的映射如下（与电话按键相同）。注意1不对应任何字母。
示例一：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例二：
输入：digits = ""
输出：[]
示例三：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
【算法设计思想】
本题主要是用到了DFS，即深度优先搜索的思想。在此我们需要搞清楚DFS的基本思想和伪代码是怎么样的。
DFS的算法设计思想：一种用于遍历或搜索树或图的算法。DFS的基本思想是从根节点开始（选择某个搜索起始节点），先尽可能深的搜索树的分支，如果到底了（即到达一个叶子节点或者当前节点没有任何未访问的子节点），就回溯到上一层，继续尽可能深的搜索其它未搜索过的子节点，这个过程一直持续到所有的节点都被访问过为止。
伪代码如下：
procedure DFS(G,V):
make V as visited;
for each w in G.adjacent(v) do //遍历v的所有邻接顶点
ifw is not visited then
DFS(G,w)//递归访问w
我们可以把这个问题看成是一个搜索的问题，在这里，2对应abc，3对应def，我们只需要求其组合就可以了，本质上是一个树形的结构，我们对这个树进行DFS即可得到答案，所以通过本题我们要复习DFS这个知识点。
【算法描述】
C++：
class Solution
{
public:
// 存储结果的容器
std::vector<std::string> ans;
// 字符串映射数组，对应数字键上的字母
std::string strs[10] = {",", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"};
// 主要的方法，用于获取电话号码的字母组合
std::vector<std::string> letterCombinations(std::string digits)
{
// 如果输入的数字字符串为空，则直接返回空的结果集
if (digits.empty())
{
return ans;
}
// 从第一个数字开始深度优先搜索
dfs(digits, 0, "");
// 返回所有可能的组合
return ans;
}
// 深度优先搜索 (DFS) 辅助方法
void dfs(const std::string &digits, int idx, std::string combine)
{
// 当前索引等于输入字符串的长度时，说明已经处理完了一个完整的组合
if (idx == digits.length())
{
// 将当前组合加入结果集中
ans.push_back(combine);
return;
}
// 获取当前数字对应的字母字符串
const std::string &s = strs[digits[idx] - '0'];
// 遍历当前数字对应的字母字符串
for (size_t i = 0; i < s.length(); i++)
{
// 将当前字母添加到组合字符串中
combine.push_back(s[i]);
// 递归地进行下一步搜索
dfs(digits, idx + 1, combine);
// 回溯：移除最后一个字符，以便尝试下一个字母
combine.pop_back();
}
}
};
Java:
import java.util.ArrayList;
import java.util.List;
class Solution {
// 存储结果的容器
private List<String> ans = new ArrayList<>();
// 字符串映射数组，对应数字键上的字母
private String[] strs = {",", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
// 主要的方法，用于获取电话号码的字母组合
public List<String> letterCombinations(String digits) {
// 如果输入的数字字符串为空，则直接返回空的结果集
if (digits.isEmpty()) {
return ans;
}
// 从第一个数字开始深度优先搜索
dfs(digits, 0, "");
// 返回所有可能的组合
return ans;
}
// 深度优先搜索 (DFS) 辅助方法
private void dfs(String digits, int idx, String combination) {
// 当前索引等于输入字符串的长度时，说明已经处理完了一个完整的组合
if (idx == digits.length()) {
// 将当前组合加入结果集中
ans.add(combination); // 修改为 add 而不是 append
return;
}
// 获取当前数字对应的字母字符串
String s = strs[digits.charAt(idx) - '0']; // 使用 charAt 获得字符而不是使用索引
// 遍历当前数字对应的字母字符串
for (int i = 0; i < s.length(); i++) {
// 将当前字母添加到组合字符串中
combination += s.charAt(i); // 使用 += 添加字符
// 递归地进行下一步搜索
dfs(digits, idx + 1, combination);
// 回溯：移除最后一个字符，以便尝试下一个字母
combination = combination.substring(0, combination.length() - 1); // 使用 substring 方法回溯
}
}
}
Python:
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 结果容器
ans: List[str] = []
# 字符串映射字典，对应数字键上的字母
strs = {
",": "",
"": "",
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
# 如果输入的数字字符串为空，则直接返回空的结果集
if not digits:
return ans
# 深度优先搜索 (DFS) 辅助方法
def dfs(digits: str, idx: int, combination: str):
# 当前索引等于输入字符串的长度时，说明已经处理完了一个完整的组合
if idx == len(digits):
ans.append(combination)
return
# 获取当前数字对应的字母字符串
s = strs[digits[idx]]
# 遍历当前数字对应的字母字符串
for i in range(len(s)):
# 将当前字母添加到组合字符串中
combination += s[i]
# 递归地进行下一步搜索
dfs(digits, idx + 1, combination)
# 回溯：移除最后一个字符，以便尝试下一个字母
combination = combination[:-1]
# 从第一个数字开始深度优先搜索
dfs(digits, 0, "")
# 返回所有可能的组合
return ans