題目網址：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/

題意：給一 string 包含數字 2-9, 以任意順序返回所有它所能表示的英文組合。
數字到英文的 mapping 如下, 其中數字 1 不對應任何字母

Solution：

想法：利用 DFS + Backtracking

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) {
            return {};
        }
        dfs(digits, 0, digits.size());
        return res;
    }

private:
    string cur;
    vector<string> res;
    vector<string> mapping = {
        "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };

    void dfs(string& digits, int i, int n){
        if (i == n) {
            res.emplace_back(cur);
            return;
        }

        for (const auto& ch : mapping[digits[i] - '2']) {
            cur += ch;
            dfs(digits, i + 1, n);
            cur.pop_back();
        }
    }
};
  • time：$O(n \cdot 4^n)$
    • 一個數字最多 4 種選擇（數字 7 和 9）
    • 總共 $4^n$ 種排列, 建構每一種需 $O(n)$
  • space：$O(n)$ ➔ 若不考慮要返回的 array res, 則取決於遞迴深度, 最大遞迴深度為 n