电话号码的自由组合

17. 电话号码的字母组合 - 力扣（LeetCode）

给定一个仅包含数字 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'] 的一个数字。

解题一：递归

这些题目还没有涉及到什么算法，第一想到的是暴力解决，话不多说，直接来递归

class Solution {
private:
    const string numbers[10] = {"",    "",    "abc",  "def", "ghi",
                                "jkl", "mno", "pqrs", "tuv", "wxyz"};
                                //创建数字和字母之间的映射关系
public:
    string s;
    vector<string> result;
    void dfs(const string& digits, int index) {
        if (index == digits.size()) {  //递归一层结束的条件
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';  //将string转换为int
        string letters = numbers[digit];  //将string暂存
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);  //存放到string的末尾
            dfs(digits, index + 1);  //递归
            s.pop_back();  //回溯
        }
    }
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0)
            return {};
        dfs(digits, 0);
        return result;
    }
};

解题二：for循环

我第一次做这个问题时，想使用for来写，但是我有一个问题，就是我不知道for内部要嵌套几层循环，如果digits.size() = 2 ，那么我就要嵌套两层循环，为3，就要嵌套三层循环，那这样不就无法写了吗，所以我转战递归，但是细想也可以。

我们可以使用 string 的拼接啊，先将当前数字代表的字母，全部暂存到result里，然后与下一个数字所代表的字母进行排列拼接（本人比较菜，所以对这种方式并不熟悉，常常感觉到很别扭）

class Solution {
private:
    const string numbers[10] = {"",    "",    "abc",  "def", "ghi",
                                "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) {  //如果为空，直接return
            return {};
        }

        vector<string> result;
        result.push_back("");

        for (char digit : digits) {  //遍历digits中的每一个元素
            vector<string> temp;
            string letters = numbers[digit - '0'];
            for (char letter : letters) {  //遍历letters中的每一个元素
                for (string s : result) {  //遍历当前result中的元素
                    temp.push_back(s + letter);  //拼接
                }
            }
            result = temp; //更新result
        }

        return result;
    }
};