LeetCode 17. Letter Combinations of a Phone Number [Medium] [C++] 解題筆記

給定一個由 2-9組成的字串 s，其中 2-9 分別可以對應到幾個特定字母如下圖:

題目要求我們找出 s 可以對應到的所有字母組合。

EX:

        Input: "23"

        Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

想法:

        這題就是典型的 DFS 應用拉，首先利用 hashmap 建立一個 數字=>字母的對應， 之後就是常規的 DFS 寫法，遍歷每個數字可能的字母搭配。這題比較有挑戰的是用 iterative 的方式來實作，DFS 的方法很直覺，iterative 就不是很容易想。

完整程式碼:

解法一:(recursive):

class Solution {

public:

    vector<string> ans;

    void dfs(vector<string>& map, vector<int>& selected, string cur) {

        if (cur.size() == selected.size()) {

            ans.emplace_back(cur);

            return;

        }

        auto idx = selected[cur.size()];

        for (int i = 0; i < map[idx].size(); i++) {

            //cout<<"map[i]: "<<map[idx][i]<<endl;

            cur.push_back(map[idx][i]);

            dfs(map, selected, cur);

            cur.pop_back();

        }

    } 

    vector<string> letterCombinations(string digits) {

        if (digits.empty()) { return {}; }

        vector<string> map(8);

        map[0] = "abc";

        map[1] = "def";

        map[2] = "ghi";

        map[3] = "jkl";

        map[4] = "mno";

        map[5] = "pqrs";

        map[6] = "tuv";

        map[7] = "wxyz";

        

        auto d = stoi(digits);

        vector<int> selected;

        while (d > 0) {

            selected.emplace_back(d % 10 - 2);

            d = d / 10;

        }

        reverse(selected.begin(), selected.end());

        //sort(selected.begin(), selected.end());

        dfs(map, selected, "");   

        return ans;

    }

};

解法二(iterative):

class Solution {

public:

    vector<string> letterCombinations(string digits) {

        if (digits.empty()) { return {}; }

        vector<string> map(8);

        map[0] = "abc";

        map[1] = "def";

        map[2] = "ghi";

        map[3] = "jkl";

        map[4] = "mno";

        map[5] = "pqrs";

        map[6] = "tuv";

        map[7] = "wxyz";

        auto d = stoi(digits);

        vector<int> selected;

        while (d > 0) {

            selected.emplace_back(d % 10 - 2);

            d = d / 10;

        }

        reverse(selected.begin(), selected.end());

        //sort(selected.begin(), selected.end());

        vector<string> ans;

        string cur(selected.size(), 'x');

        int idx = 0;

        vector<int> prev(selected.size(), 0);

        while (idx >= 0) {

            if (idx == selected.size()) {

                ans.emplace_back(cur);

                --idx;

                prev[idx]++;

            }

            else {

                if (prev[idx] == map[selected[idx]].size()) {

                    prev[idx] = 0;

                    if (--idx < 0) { break; }

                    prev[idx]++;

                }

                else {

                    cur[idx] = map[selected[idx]][prev[idx]];

                    idx++;

                }

            }

        }        

        return ans;

    }

};