【4.10】图搜索算法-BFS和DFS解电话号码的字母组合

一、题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

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

示例 2：

输入：digits = ""
输出：[]

示例 3：

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

提示：

0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

二、解题思路

BFS思路：

每一个数字对应3到4个字符，我们以示例一为例画个图来看一下

我们看到实际上就是一颗n叉树，除了叶子节点外，每个节点都有3到4个子节点。对于二叉树的BFS遍历如下图所示，也就是一行一行的访问

由于每个节点最多有两个子节点，因此我们可以将其视为二叉树。如果每个节点最多有n个子节点，我们可以称之为n叉树。对于n叉树，由于子节点较多，我们无法一次性全部列出，因此可以使用for循环来遍历。实际上，这道题并没有给出一棵真正的树，这棵树只是我们想象出来的。那么，我们如何确定何时到达叶子节点呢？实际上很简单，如果有n个数字，那么叶子节点的字符串长度就应该为n。

DFS思路：

对于树的遍历，除了广度优先搜索（BFS）之外，我们还可以使用深度优先搜索（DFS）。在这里，我们可以将其视为树的前序遍历。网上有人称这种算法为回溯算法，但实际上，在这里回溯时并不需要撤销选择，因为每次生成字符串时都会创建一个新的对象，因此不会对其他分支造成污染。

三、代码实现

BFS方式代码：

#include <iostream>
#include <vector>
#include <string>
#include <queue>using namespace std;vector<string> letterCombinations(string digits) {vector<string> res;// 空判断if (digits.empty())return res;char tab[8][4] = {{'a', 'b', 'c', '\0'}, {'d', 'e', 'f', '\0'}, {'g', 'h', 'i', '\0'},{'j', 'k', 'l', '\0'}, {'m', 'n', 'o', '\0'}, {'p', 'q', 'r', 's'},{'t', 'u', 'v', '\0'}, {'w', 'x', 'y', 'z'}};queue<string> q;q.push("");while (!q.empty()) {string current = q.front();q.pop();if (current.length() == digits.length()) {res.push_back(current);} else {char* chars = tab[digits[current.length()] - '2'];for (int i = 0; chars[i] != '\0'; i++) {q.push(current + chars[i]);}}}return res;
}int main() {string digits = "23";vector<string> result = letterCombinations(digits);cout << "Letter combinations for " << digits << " are:" << endl;for (const string& combination : result) {cout << combination << " ";}cout << endl;return 0;
}

DFS方式代码：

#include <iostream>
#include <vector>
#include <string>using namespace std;void dfs(vector<string>& res, int index, const string& digits, const char tab[8][4], string path) {// 到叶子节点了，就把这条路径选择的字符添加到res中if (path.length() == digits.length()) {res.push_back(path);return;}char* chars = tab[digits[index] - '2'];// 访问当前节点的所有子节点for (int i = 0; chars[i] != '\0'; i++) {dfs(res, index + 1, digits, tab, path + chars[i]);// 因为字符串是创建了一个新的对象，所以这里不需要撤销}
}vector<string> letterCombinations(const string& digits) {vector<string> res;if (digits.empty())return res;char tab[8][4] = {{'a', 'b', 'c', '\0'}, {'d', 'e', 'f', '\0'}, {'g', 'h', 'i', '\0'},{'j', 'k', 'l', '\0'}, {'m', 'n', 'o', '\0'}, {'p', 'q', 'r', 's'},{'t', 'u', 'v', '\0'}, {'w', 'x', 'y', 'z'}};dfs(res, 0, digits, tab, "");return res;
}int main() {string digits = "23";vector<string> result = letterCombinations(digits);cout << "Letter combinations for " << digits << " are:" << endl;for (const string& combination : result) {cout << combination << " ";}cout << endl;return 0;
}