# 【LeetCode】 17. Letter Combinations of a Phone Number

## Description
> Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
> A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
> Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

> 給一串包含數字 2-9 的字串，回傳所有可能出現的字母組合。
> 每個數字到字母的對應表在下方(就像手機按鈕一樣)，記住1沒有對應到任何字母。
> 注意：
> 雖然範例中的答案有按字典排序，但實際上你可以用任何順序。


## Example:

Example:

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

## Solution

* 用一個`vector<string>`當作對應表，1的部分放入空字串就可以了。
* 每次放入一個字母，用迴圈去放下一種字母(同一個按鈕)；用遞迴去放下一個字母(下一個按鈕)。
* 注意如果輸入是空的，不可回傳任何空字串。

### Code

class Solution {
public:
    
    void addLetter(string dights, string word, vector<string>& ans)
    {
        vector<string> btn = {"", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(dights.empty())
        {
            if(!word.empty())
                ans.push_back(word);
        }
        else
        {
            for(int i = 0; i < btn[dights[0] - '1'].size(); i++)
            {
                addLetter(dights.substr(1), word + btn[dights[0] - '1'][i], ans);
            }
        }
    }
    
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        addLetter(digits, string(), ans);
        return ans;
    }
};

###### tags: `LeetCode` `C++`