> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/17.-letter-combinations-of-a-phone-number.md).

# 17. Letter Combinations of a Phone Number

## 1.問題

![](/files/-LLxv612KCQ4ukbJObi_)

## 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();
        }
    }
};
```