一、题目
给定一个仅包含数字 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;
}