【回溯+剪枝】电话号码的字母组合 && 括号生成
【回溯+剪枝】电话号码的字母组合 && 括号生成
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]示例 2：
输入：digits = ""
输出：[]示例 3：
输入：digits = "2"
输出：["a","b","c"]提示：
0 <= digits.length <= 4digits[i]是范围['2', '9']的一个数字。
解题思路：回溯 + 哈希表
这道题其实就是暴力搜索，要遍历所有的叶子节点拿到所有的结果。其中因为每个位置可选择的字符与其他位置并不冲突，因此不需要标记已经出现的字符，只需要将每个数字对应的字符依次填入字符串中进行递归，然后在回溯时候进行撤销之前的填入操作即可。
只不过为了快速找到当前数字对应的字母组合，我们需要在递归之前我们需要定义一个 哈希表 hash，记录 2~9 各自对应的字符。（但实际上在实现的时候，为了方便我们可以直接给出 10 个元素大小的字符串数组即可，其中 0 和 1 都是空串！
接下来的步骤其实就和全排列问题是类似的，要下标 0 处开始遍历所有的结果！只不过要注意的是递归函数出口的细节，因为有可能这道题传入的手机号码是空串，此时题目要求如果是空串的话，返回的结果是什么都没有，所以我们就需要在递归函数出口处判断一下，如果电话号码不是空串再进行添加结果集操作！
class Solution {
private:
string hash[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
vector<string> ret; // 存放结果集
string path; // 存放路径上的字符
public:
vector<string> letterCombinations(string digits) {
dfs(digits, 0);
return ret;
}
void dfs(string& digits, int index)
{
// 递归函数出口
if(index == digits.size())
{
if(digits.size() > 0)
ret.push_back(path);
return;
}
string tmp = hash[digits[index] - '0']; // 先拿到当前数字对应的字符串
for(int i = 0; i < tmp.size(); ++i)
{
// 处理当前节点
path.push_back(tmp[i]);
// 先递归处理该节点下面的其它路径
dfs(digits, index + 1);
// 进行回溯处理
path.pop_back();
}
}
};22. 括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]示例 2：
输入：n = 1
输出：["()"]提示：
1 <= n <= 8
解题思路：回溯 + 剪枝
这道题其实就是一个暴力搜索，我们在搜索之前还需要知道有效的括号组合的要求：
- 左括号数量 = 右括号数量 =
n。 - 在遍历途中，保证三个小要求：
- 左括号数量不超过
n。 - 右括号数量不超过
n。 - 左括号数量一定要大于等于右括号数量，才能保证右括号至少有一个左括号与之匹配。
- 左括号数量不超过
知道了有效的括号组合要求之后，就是开始构建一棵决策树，其实就是每次看选左括号还是右括号，然后选完之后再递归继续选，直到最后符合上述的要求为止，决策树如下图所示，以 n=2 为例：
所以为了达到剪枝的效果，我们需要有一个 left 和一个 right 变量，来记录当前左括号和右括号的数量，如果不符合上述的要求的话直接就剪枝了！
然后在递归的时候，如果选择的是左括号的话，则让 left+1，如果选择的是右括号的话则让 right+1 去递归，这里我们将这两个变量设为局部变量，这样子每一层的 left 和 right 就不会互相干扰，就不用在回溯的时候进行处理！
剩下的细节都是一样的，具体参考代码！
class Solution {
private:
vector<string> ret; // 存放结果集
string path; // 存放当前路径的字符串
public:
vector<string> generateParenthesis(int n) {
dfs(n, 0, 0);
return ret;
}
void dfs(int n, int left, int right)
{
// 递归函数出口
if(left > n || right > n || right > left)
return;
// 如果满足括号数量则添加结果集并且返回
if(left == n && right == n)
{
ret.push_back(path);
return;
}
string tmp = "()";
for(int i = 0; i < tmp.size(); ++i)
{
// 处理当前节点
path.push_back(tmp[i]);
// 递归后面的路径
if(tmp[i] == '(')
dfs(n, left + 1, right);
else
dfs(n, left, right + 1);
// 回溯处理
path.pop_back();
}
}
};腾讯云开发者
