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
题意
给定一个包含2到9的数字串，每个字母能代表一些字母，对应于电话按钮上的数字和字母，求数字串能表示的所有字母组合。输出顺序任意。
题解
就是一个组合问题，可以使用递归来处理。假设digits代表数字串，s(digits)为数字串能表示的字母串。那么s(digits) = letter(digits[0]) + s(digits[1...n-1])。
时间复杂度：$T(n) = T(n-1) + n$，为$O(n^2)$。
代码
- 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日 星期四