LeetCode Problem: Letter Combinations of a Phone Number 詳解

Description

給定一個包含 2-9 的數字字串，並根據電話按鍵的圖片，將數字對應到英文字母，回傳所有可能的英文字串之排列組合。

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Solution

本題算是相對簡單的 Medium 題目，首先我們可以根據電話按鍵建構一個 mapping table，利用一個長度為 8 的 vector array，紀錄對應的英文字母：[{'a', 'b', 'c'}, {'d', 'e', 'f'}, ...]，例如當我們發現 digit 為 d = '3'，可以利用 d 與 '2' 的距離，找到對應的英文字母 table[d - '2']。接下來我們可以利用 for 迴圈或是 recursion 的方式求得答案。

Solution 1 – for loop
以下說明如何用 for 迴圈解題，假設我們得到 digits = "23"，我們需要兩個 vector 容器 vector<string> ans 以及 vector<string> tmp，分別保存目前的所有組合，以及暫時紀錄加上下個 digit 的所有組合。在初始狀態時我們必須先將空字串 "" 放入 vector<string> ans 內，再開始 for 迴圈。

每次的迴圈步驟都會相同。首先我們會持續迭代得到下一個 digit，以我們的例子 d = '2'，可以得到對應的字母 table[d - '2'] = {'a', 'b', 'c'}。我們的目標是要將 ans 裡面所有的字串方別加上 {'a', 'b', 'c'}，要做到這個目標我們需要兩個 for 迴圈，第一個 for 迭代 ans 裡現有的字串，第二個 for 則是依序迭代對應的英文字母 {'a', 'b', 'c'}，我們把從 ans 讀出的字串以及某個英文字母串接，並將這個結果推入另一個暫時的容器 vector<string> tmp，此時我們可以得到 tmp = {"a", "b", "c"}。最後我們將暫時的容器寫回答案 ans = move(tmp)，注意這裡可以利用 std::move 做移動的動作，避免多次 copy construct 導致效能降低，或是增加記憶體使用量。接下來我們繼續處理下一個字母，再重複相同的步驟，直到所有字母都被我們處理過，即可跳出迴圈。

Solution 2 – recursion
除了 for 迴圈之外，我們也可以利用 recursive (DFS)的方式解題。首先我們需要有一個字串 accumulate 紀錄我們的暫時結果，並且我們需要一個 idx 紀錄我們走到第幾個 digit。我們以 digits = "234" 為例，我們從第一個 digit '2' 開始，此時 idx = 0, accumulate = ""，並且有三個字母 {'a', 'b', 'c'} 需要考慮，因此在第一層 recursion 內我們需要用 for 迭代三個字母，對於這一層的每個字母 d，我們紀錄 idx += 1, accumulate += d 並且將這些紀錄送到第二層的 recursion 後，再繼續處理下一個字母並再次傳送。

在第二層的 recursion 中我們遇到三個英文字母 {'d', 'e', 'f'}，我們一樣迭代每個英文字母，並且將 idx += 1, accumulate += d 送到第三層，假設第一層的 accumulate = "a" 送到這層，我們會將 accumulate = "ad"、accumulate = "ae"、accumulate = "af"，搭配 idx = 2 送到下一層。

最後一層我們會遇到三個英文字母 {'g', 'h', 'i'}，重複相同的做法，假設第二層的 accumulate = "ad" 傳到這裡，我們迭代三個英文字母可以得到 accumulate = "adg"、accumulate = "adh"、accumulate = "adi"。唯一不同的是我們依據 idx 判斷出我們已經到達最後一層，所以就不再繼續送到下一層，而是將目前的 accumulate 推入我們的 vector<string> result 裡面，作為其中一個答案。

完整程式碼如下：

// Solution 1 - for loop
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return vector<string>();

        vector<vector<char>> phone_map = {
            {'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> ans = {""};
        vector<string> tmp;
        for (auto &d: digits)
        {
            for (auto &s: ans)
            {
                for (auto &c: phone_map[d - '2'])
                {
                    tmp.push_back(s + c);
                }
            }
            ans = move(tmp);
            tmp = {};
        }

        return ans;

    }
};

//Solution 2 - recursion
class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size()==0)
        {
            return vector<string>();
        }

        vector<char> table[8];
        table[0] = {'a', 'b', 'c'};
        table[1] = {'d', 'e', 'f'};
        table[2] = {'g', 'h', 'i'};
        table[3] = {'j', 'k', 'l'};
        table[4] = {'m', 'n', 'o'};
        table[5] = {'p', 'q', 'r', 's'};
        table[6] = {'t', 'u', 'v'};
        table[7] = {'w', 'x', 'y', 'z'};

        vector<string> answer;
        backtrack(digits, table, 0, answer, "");
        return answer;

    }

    void backtrack(const string &digits, const vector<char> (&table)[8], int idx, vector<string> &result, string accumulate)
    {
        for (auto it=table[digits[idx] - '2'].begin(); it!=table[digits[idx] - '2'].end(); ++it)
        {
            if (idx==digits.size() - 1)
            {
                result.push_back(accumulate + *it);
            }
            else
            {
                backtrack(digits, table, idx + 1, result, accumulate + *it);
            }
        }
    }
};

Description

Solution

1 Comment