题目内容

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。

注意： 1 不对应任何字母。

示例

示例 1：

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

示例 2：

输入：digits = “”
输出：[]

示例 3：

输入：digits = “2”
输出：[“a”,”b”,”c”]

提示

1、0 <= digits.length <= 4
2、digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

题解

本题采用深度优先遍历的算法进行求解，在实现上使用递归的思想。

我们需要实现一个dfs的递归函数，其中需要知道给出的数字串、确定当前递归哪一位以及当前未完全遍历好的答案字符串。具体见注释说明即可~

代码

class Solution {
public:
    vector<string> ans;
    string strs[10] = {
      			//使用字符串数组模拟手机位置上的按键
            "","","abc","def",
            "ghi","jkl","mno",
            "pqrs","tuv","wxyz"
        };

    vector<string> letterCombinations(string digits) {
        if(digits.empty()) return ans;
        dfs(digits,0,"");//给定初始值，然后开始递归即可。
        return ans;
    }
    //u表示当前遍历的层的深度，path为路径
    void dfs(string& digits, int u, string path){
        if(u == digits.size()) ans.push_back(path); //如果深度达到最大，则答案加上这一次的路径结果
        else{
            //否则，根据strs，求出对应数字代表的字母的字符串,然后用for循环一个一个枚举。
            for(auto c: strs[digits[u] - '0']){
                dfs(digits,u+1,path+c);
            }
        }
    }
};