【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;
}