个人建站程序,手机网站建设wap,wordpress主题投稿,网站主机免费目录
题目
方法一
思路
代码 题目
17. 电话号码的字母组合
难度#xff1a;中等
给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对…目录
题目
方法一
思路
代码 题目
17. 电话号码的字母组合
难度中等
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]
示例 2
输入digits
输出[]
示例 3
输入digits 2
输出[a,b,c]
方法一
思路
这是一个经典的回溯问题我们先来分析一下这道题的暴力解法。暴力解法很容易想到通过给定的字符串的数字个数和每个数字对应的字母我们使用循环遍历然后存储下来加入返回数组这是一个简单的穷举算法。
我们可以使用回溯算法优化每个回溯算法都可以抽象为树形结构。 根节点代表算法的起始点没有任何决策相当于回溯树的顶部。 分支从每个节点延伸出的边表示可能的决策或选择。在选择一个选项后算法沿着相应的分支向下移动到树的下一层。 叶子节点代表算法的最终状态通常是找到了问题的解或者是达到了问题空间的边界。 回溯边当算法在某个分支上探索到尽头即该路径不是解的一部分时它会通过回溯边返回到上一个决策点尝试其他选项。 深度优先搜索回溯算法通常采用深度优先搜索DFS策略即尽可能深地探索树的分支直到找到解或确定该分支不包含解。 剪枝在某些情况下可以提前判断某个分支不可能是解的一部分从而剪掉这个分支减少不必要的计算。 路径从根节点到叶子节点的路径代表一个完整的解决方案或者在电话号码的字母组合问题中代表一个完整的字母组合。 状态存储在树的每个节点上都需要存储足够的状态信息以便在回溯时能够恢复到之前的决策状态。
以本题为例树的根节点没有字母每个数字对应一层每层的节点数等于该数字可以映射到的字母数。从每个节点延伸出的边代表选择一个特定的字母叶子节点代表一个完整的字母组合。
以字符串 23 为例他对应的回溯树结构如下 我们用递归模拟树的遍历在遍历到每层结点时将其加入字符串。在递归到递归出口时就是遍历到叶子结点此时就是完整组合。我们将其加入返回数组。
以为我们要的是全部组合所以不需要剪枝。
在递归返回后我们会从字符串中弹出一个字符对应的是回溯的过程。
代码
class Solution {
public:string s;vectorstring board{,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};void dfs(int index,string digits,vectorstring ret){if(index digits.size()){ret.push_back(s);return;}int zdigits[index]-0;for(int i0;iboard[z].size();i){s.push_back(board[z][i]);//递归dfs(index1,digits,ret);//回溯s.pop_back();}}vectorstring letterCombinations(string digits) {vectorstring ret;if(digits.empty()){return ret;}dfs(0,digits,ret);return ret;}
};
注意在 letterCombinations 如果digits为空需要返回不然在 dfs中会加入一个空串。
