# [leetcode题解]17. Letter Combinations of a Phone Number

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.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

```输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
```

```class Solution {
private:
void dfs(string &digits, int idx, string &s, vector<string> &res) {
int i = 0;
string tmp = "";

if (idx >= digits.length()) {
res.push_back(s);
return;
}

tmp = map[digits[idx] - '0'];
for (i = 0; i < tmp.length(); i++) {
s.push_back(tmp[i]);
dfs(digits, idx + 1, s, res);
s.pop_back();
}
}

string map[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
vector<string> letterCombinations(string digits) {
vector<string> res;
string s = "";

if (digits.length() == 0)
return res;

dfs(digits, 0, s, res);
return res;
}
};```