建设银行互联网站,旅游网站首页制作,wordpress简介,珠海网站定制一、题目描述给定一个仅包含数字 2-9 的字符串#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下#xff08;与电话按键相同#xff09;。注意 1 不对应任何字母。示例 1#xff1a;输入#xff1a;digits 23输出…一、题目描述给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。示例 1输入digits 23输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2输入digits 输出[]示例 3输入digits 2输出[a,b,c]来源力扣LeetCode链接https://leetcode.cn/problems/letter-combinations-of-a-phone-number著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。二、运行结果三、解题思路这里是参考官方给出的解题思路本人想的也是用回溯法但是奈何不懂回溯怎么写org仅以此博文记录权当加深理解。首先用一个哈希表将每个数字对应的字母串然后进行回溯遍历具体如下如果当前字母组合的长度和原数字串的长度相等则表示已经得到了一个满足的字母组合将该字母串加入到结果列表中递归出口如果不相等表示还没有遍历完数字串则取出当前下标的数字根据数字从哈希表中取出其对应的字母串获取这个字母串的长度字母个数然后对这个字母串的每个字母进行处理首先出去该字母然后将该字母加入到作为参数传递的字母串后面再递归对下一个数字进行同样的处理最后是回溯将当前字母从字母串中删除避免重复遍历。ps: 回溯是通过递归实现的所以最前面要定义递归出口最重要的是在要在递归后面删掉当前字母这就是回溯。四、AC代码class Solution {public ListString letterCombinations(String digits) {int len digits.length();ListString ans new ArrayList();if(len 0) return ans;//双花括号初始化 匿名内部类 初始化块MapCharacter, String numMap new HashMap(){{put(2, abc);put(3, def);put(4, ghi);put(5, jkl);put(6, mno);put(7, pqrs);put(8, tuv);put(9, wxyz);}};StringBuffer sb new StringBuffer();trackback(digits, numMap, ans, 0, sb);return ans;}//回溯用递归的方式实现public void trackback(String digits, MapCharacter, String phoneMap, ListString ans, int index, StringBuffer sb){if(index digits.length()){ans.add(sb.toString());} else {char num digits.charAt(index);String letters phoneMap.get(num); //当前数字对应的字母串int letCount letters.length(); //当前数字对应的字母个数for(int i0; iletCount; i){char c letters.charAt(i);sb.append(c); //加入当前字母trackback(digits, phoneMap, ans, index1, sb); //递归处理下一个数字sb.deleteCharAt(index); //回溯}}}
}
