leetcode17：电话号码的字母组合

题目链接

leetcode

题目描述

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

C++ 代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

/*
    回溯法，深度优先搜索

    时间复杂度：O(3^m*4^n)
        其中 m 是输入中对应 3 个字母的数字个数，n 是输入中对应 4 个字母的数字个数。
        当输入包含 m 个对应 3 个字母的数字和 n 个对应 4 个字母的数字时，
        不同的字母组合一共有 3^m*4^n 种，需要遍历每一种字母组合。
    空间复杂度：O(m+n)
        除了返回值以外，主要取决于哈希表以及回溯过程中的递归调用层数。
        哈希表的大小与输入无关，递归调用层数最大为 m+n。
*/
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        res.clear();
        path.clear();
        
        if (digits.empty()) {
            return res;
        }

        dfs(digits, 0); // 第 0 个字符开始，进行深度优先搜索

        return res;
    }

    void dfs(const string& digits, int index) {
        // 结束条件：当前处理的位置等于字符串长度，说明找到了一个完整组合
        if (digits.size() == index) {
            res.push_back(path);
            return;
        }

        int digit = digits[index] - '0';
        string letters = num2str[digit];
        // 遍历该数字对应的所有字母
        for (int i = 0; i < letters.size(); i++) {
            path.push_back(letters[i]); // 选择当前字母，加入路径
            dfs(digits, index + 1);     // 递归处理下一个数字字符
            path.pop_back();            // 回溯：撤销上一步的选择，尝试下一个字母
        }
    }

private:
    string num2str[10] = {
        "", "", "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
    vector<string> res;
    string path;
};

// 辅助函数：打印二维数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "\"" << nums[i] << "\"";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<string> digits_cases = {
        "23",
        "",
        "2",
    };

    for (int i = 0; i < digits_cases.size(); i++) {
        string digits = digits_cases[i];
        vector<string> result = solution.letterCombinations(digits);

        cout << "Input: \"" << digits << "\"\n";
        cout << "Output: ";
        printArray(result);
    }

    return 0;
}