组合问题——LeetCode题目17：电话号码的字母组合
组合问题——LeetCode题目17：电话号码的字母组合
原题描述
+
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例
输入：“23”
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
原题链接：https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number
思路解析
+
本质上此题等价于————给定若干个集合，从每个集合中挑选一个元素，求所有可能的组合情况。
我希望你能有一个刷题经验：凡是涉及到排列组合的题目，基本都可以通过递归解决。因为不管是排列还是组合，都是从先求子问题，然后再求原问题。递推和递归是数学和编程中非常重要的思想，多写多练才会有感觉。
回到题目，我们开始从最简单的情况开始分析。
1. 最原子问题——只有一个集合时
这是显而易见的，假设集合 ，那么直接返回即可。
2. 最简单的特殊情况——当给定两个集合时
假设集合 ，要让集合 中的每个元素和集合 中的每个元素两两相碰，因此返回的是 ，一个二重循环就能搞定。
3.从特殊到一般——当给定多个集合时
先假设只有三个集合 ，不跳步的做法是，先求 和 的组合情况，返回一个新的集合 ，然后再做 和 的组合情况即为所求。集合数量再增加之后，思路也是一样的。
所以我们总能把原问题逐步拆解成子问题来求解，这就是此题的递推关系。假设 表示从第 个集合到第 个集合的组合结果， 表示第 个集合，那么有如下递推关系：好了，现在你可以写代码了。虽然递归程序的时间复杂度并不是最优的，但递归程序确实能够显示出一个人对问题的理解深度，分而治之是算法中的常用策略，希望大家多多练习。
这道题你会了，那么请你思考另一个问题——全排列应该怎么求？
复杂度分析
+
- 时间复杂度：
- 空间复杂度：
C++参考代码
+
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> res;
map<char, string> table = {
{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}
};
if (!digits.size()) return res;
else if (digits.size() == 1) {
for (int i = 0; i < table[digits[0]].size(); ++i) {
string tmp(1, table[digits[0]][i]);
res.push_back(tmp);
}
return res;
}
vector<string> suffix = letterCombinations(digits.substr(1, digits.size() - 1));
for (int i = 0; i < table[digits[0]].size(); ++i) {
for (int j = 0; j < suffix.size(); ++j) {
string tmp = "";
tmp += table[digits[0]][i];
tmp += suffix[j];
res.push_back(tmp);
}
}
return res;
}
};
腾讯云开发者
