17. Letter Combinations of a Phone Number

1.問題

2.想法

• 提問

• function header, parameter

• test input

  • edge case

• 說明想法

  • 有n位數, 每個位數有m個選擇, 求其排列組合-> ray tracking

    • 參考46.Permutations (Medium), 47.Permutations II (Medium)

• 測試計算複雜度: O(n^2) ?

3.程式碼

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        if (digits.empty()) {
            return res;
        }
        vector<vector<char>> v;
        v.push_back({' '});
        v.push_back({' '});
        v.push_back({'a', 'b', 'c'});
        v.push_back({'d', 'e', 'f'});
        v.push_back({'g', 'h', 'i'});
        v.push_back({'j', 'k', 'l'});
        v.push_back({'m', 'n', 'o'});
        v.push_back({'p', 'q', 'r', 's'});
        v.push_back({'t', 'u', 'v'});
        v.push_back({'w', 'x', 'y', 'z'});
        int size = digits.size();
        string record = "";
        helper(v, digits, record, 0, res);
        
        return res;
    }
private:
    void helper(vector<vector<char>> v, string digits, string record, int startIndex, vector<string>& res){
        if (startIndex == digits.length()){
            res.push_back(record);
            return;
        }
        int index = (int)(digits[startIndex] - '0');
        for (int i = 0; i < v[index].size(); i++) {
            record.push_back(v[index][i]);
            helper(v, digits, record, startIndex + 1, res);
            record.pop_back();
        }
    }
};