【回溯+剪枝】电话号码的字母组合括号生成

文章目录

17. 电话号码的字母组合
解题思路：回溯 + 哈希表
22. 括号生成
解题思路：回溯 + 剪枝

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 <= 4
digits[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。
在遍历途中，保证三个小要求：
1. 左括号数量不超过 n。
2. 右括号数量不超过 n。
3. 左括号数量一定要大于等于右括号数量，才能保证右括号至少有一个左括号与之匹配。

知道了有效的括号组合要求之后，就是开始构建一棵决策树，其实就是每次看选左括号还是右括号，然后选完之后再递归继续选，直到最后符合上述的要求为止，决策树如下图所示，以 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();}}
};