# LeetCode17. Letter Combinations of a Phone Number（递归 / 回溯）

## LeetCode17. Letter Combinations of a Phone Number（递归）

• Medium
• Accepted：368,431
• Submissions：898,738

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.

### 链接

https://leetcode.com/problems/letter-combinations-of-a-phone-number

### 代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
• Memory Usage: 8.7 MB, less than 62.00% of C++ online submissions for Letter Combinations of a Phone Number.
class Solution {
private:
vector <string> ans;
const string letterMap[10] =
{
" ",  // 0
"",   // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};

// s中保存了此时由digits[0...index-1]得到的一个字母字符串
// 寻找和digits[index]匹配的字母，获得digits[0...index]翻译得到的解
void solve(const string & digits, int index, const string & s)
{
if (index == digits.size()) // 保存结果
{
ans.push_back(s);
return ;
}
char c = digits[index];
string letters = letterMap[c - '0'];
for (int i = 0; i < letters.size(); ++i)
solve(digits, index + 1, s + letters[i]);
}

public:
vector<string> letterCombinations(string digits) {
ans.clear();
if (digits.empty())
return ans;
solve(digits, 0, "");
return ans;
}
};

The end.
2019年4月11日 星期四