17. Letter Combinations of a Phone Number

利用dfs, 當走到字尾就加入res

跟22. Generate Parentheses的做法幾乎一樣

class Solution {
public:
    const vector<string> pn= {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    void dfs(string &digits, int i, string cur, vector<string> &res){
        if(i == digits.size()){
            res.push_back(cur);
            return;
        }
        int number = digits[i] - '0';
        for(auto c: pn[number]){
            dfs(digits, i + 1, cur + c, res);
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return {};
        string cur = "";
        vector<string> res;
        dfs(digits, 0, cur, res);
        return res;
    }
};