# 17. Letter Combinations of a Phone Number

## 1.問題

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LLxtvIbCK4aZ3u6n91G%2F-LLxv612KCQ4ukbJObi_%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-09%20%E4%B8%8B%E5%8D%886.41.18.png?alt=media\&token=2a05fc33-67d2-49d4-9ef8-39c20817e086)

## 2.想法

* 提問
* function header, parameter
* test input
  * edge case
* 說明想法
  * 有n位數, 每個位數有m個選擇, 求其排列組合-> ray tracking
    * 參考[46.Permutations (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/46.-permutations-medium), [47.Permutations II (Medium)](https://jenhsuan.gitbook.io/algorithm/leetcode/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();
        }
    }
};
```
