做特卖的网站有,域名绑定网站,wordpress 英文链接,东莞网站SEO优化托管力扣17-电话号码的数字组合 思路代码 题目链接
思路 原题#xff1a; 给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。 输… 力扣17-电话号码的数字组合 思路代码 题目链接
思路 原题 给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 输入digits “23” 输出[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”
思路 电话号码中的一个数字可以对应到多个字母例如2对应a、b、c。要求23对应的字母组合就是把2和3对应的字母进行组合。 在每次组合的过程中一个数字只能取一个字母不能连续两个字母来自同一个数字 思考 问题1如何收集一个可能的组合 问题2在收集到一种组合后如何继续收集第二种组合 对于问题1用暴力法可以解决每层循环枚举一个数字对应的字母但是电话号码串很长循环嵌套深代码不易好编写 可以采用递归的方式每层进入递归函数尝试一个数字对应的点好号码 进入函数可以想向成进入一棵树的下一层当递归的深度到达电话号码长度即到达叶子节点则返回。 问题3在递归的每一层做什么 递归纵向是进入树下一层即电话号码中的一个数字在同一层应该去枚举这个数字对应的字母这样就可以将当前层的字母与上一层的字母进行结合形成答案的一部分 问题4递归什么时候结束 到达电话号码的长度时应该往树的上一层返回。
这里的往下递和往上归即回溯法往下遍历是搜索往上是回溯回退到上一层当前数字对应的字母就丢弃了 比如 2,3; 3是第二层遍历得到的字母组合是ab, 已经达到电话号码长度往上一层回溯时b应该就被丢弃。
因此本题使用回溯法纵向遍历电话号码中的每个数字横向遍历每个数字对应的字母达到电话号码长度时收集一种组合并往上一层回溯。
代码
class Solution {private ListString ans;private String[][] dic {{2,abc},{3,def},{4,ghi},{5,jkl},{6,mno},{7,pqrs},{8,tuv},{9,wxyz}};public ListString letterCombinations(String digits) {ans new ArrayList();if (digits.length()0) {return ans;}MapString,String m new HashMap();for (int i0, ndic.length; in; i) {m.put(dic[i][0], dic[i][1]);}String path ;dfs(digits, m, 0, path);return ans;}public void dfs(String digits, MapString, String mp, int i, String path) {int n digits.length();if (in) {ans.add(new String(path));return;}String t mp.get(digits.charAt(i));for (int j0, mt.length(); jm; j) {dfs(digits, mp, i1, patht.charAt(j));}}
}
