【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']
的一个数字。
二、解题思路
由于每个节点最多有两个子节点,因此我们可以将其视为二叉树。如果每个节点最多有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;
}
原文地址:https://blog.csdn.net/linshantang/article/details/143061209
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!