題目： LeetCode - 17. Letter Combinations of a Phone Number

題目說明

給一個只包含數字的字串，表示按下手機鍵盤的號碼及順序，求所有可能出現的字串。

解題思路

先依照鍵盤及數字建表，之後使用 DFS 列出所有有可能的組合即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<string> letterCombinations(string digits)
    {
        if(digits.empty()) return {};
        vector<vector<char>> dict = {{'a', 'b', 'c'}, {'d', 'e', 'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'}};
        vector<string> v;
        dfs(string(), digits, 0, v, dict);
        return v;
    }
private:
    void dfs(string str, string& digits, int idx, vector<string>& v, vector<vector<char>>& dict)
    {
        if(idx == digits.size()) { v.emplace_back(str); return; }
        for(auto c : dict[digits[idx] - '0' - 2]) dfs(str + c, digits, idx + 1, v, dict);
    }
};