17. 电话号码的字母组合

caution

原题链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

思路

典型 DFS 题目，画出图后就可以得到一个树形的结构，因为对于每一个 a 都有对应的 d e f，从所给样例来说。所以就是典型的 DFS 题目。

代码

class Solution {
public:

    unordered_map<char, string> m;
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        m['2'] = "abc";
        m['3'] = "def";
        m['4'] = "ghi";
        m['5'] = "jkl";
        m['6'] = "mno";
        m['7'] = "pqrs";
        m['8'] = "tuv";
        m['9'] = "wxyz";
        
        if (digits.empty()) return res;

        string tmp;
        dfs(0, tmp, digits);

        return res;
    }

    void dfs(int u, string tmp, string digits) {
        if (u == digits.size()) {
            res.push_back(tmp);
        } else {
            char digit = digits[u];
            string pattern = m[digit];
            for (int i = 0; i < pattern.size(); i++) {
                tmp.push_back(pattern[i]);
                dfs(u + 1, tmp, digits);
                tmp.pop_back();
            }

        }
    }
};