LeetCode 17. 电话号码的字母组合

LeetCode 17. 电话号码的字母组合

思路：

dfs最主要的在于找到搜索的顺序，这道题的搜索顺序是对dig字符串的每个位置进行搜索，因为每个位置的数字对应的字母有多个。

代码：

class Solution {
public:
    int n;
    vector<string> res;
    string path;
    vector<string> nums = {
        "","","abc",
        "def","ghi","jkl","mno",
        "pqrs","tuv","wxyz"
    };

    vector<string> letterCombinations(string digits) {
        n = digits.size();
        if(!n) return res;
        dfs(digits,0,"");
        return res;
    }

    void dfs(string digits,int u,string path){
        if(u == digits.size()){
            res.push_back(path);
            return;
        }
        int t = digits[u] - '0';
        for(int i = 0;i < nums[t].size(); i++){
            char c = nums[t][i];
            dfs(digits,u + 1,path + c);
        }
    }
};