回溯---数字键盘组合
发布时间:2020-12-14 04:42:57 所属栏目:大数据 来源:网络整理
导读:数字键盘组合 17. Letter Combinations of a Phone Number (Medium) Input:Digit string "23"Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. 题目描述: ??根据给出的数字字符串,组成其对应手机电话键盘上的字母组合。 思路分析: ??这种求字符
数字键盘组合17. Letter Combinations of a Phone Number (Medium) Input:Digit string "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. 题目描述:??根据给出的数字字符串,组成其对应手机电话键盘上的字母组合。 思路分析:??这种求字符串排列组合的问题,我们使用回溯的思想来进行解决,首先将每个数字对应的字母,作为键值对保存在map中,然后遍历数字串,利用回溯的思想,求出组合。 代码:public List<String>letterCombinations(String digits){ List<String>res=new ArrayList<>(); if(digits==null||digits.length()==0) return res; HashMap<Character,char[]>map=new HashMap<>(); map.put('0',new char[]{}); map.put('1',new char[]{}); map.put('2',new char[]{'a','b','c'}); map.put('3',new char[]{'d','e','f'}); map.put('4',new char[]{'g','h','i'}); map.put('5',new char[]{'j','k','l'}); map.put('6',new char[]{'m','n','o'}); map.put('7',new char[]{'p','q','r','s'}); map.put('8',new char[]{'t','u','v'}); map.put('9',new char[]{'w','x','y','z'}); StringBuilder str=new StringBuilder(); //将其中的一种结果保存 findComb(digits,map,res,str); return res; } public void findComb(String digits,HashMap<Character,char[]>map,List<String>res,StringBuilder str){ if(str.length()==digits.length()){ res.add(str.toString()); return ; } for(char c:map.get(digits.charAt(str.length()))){ str.append(c);//添加 findComb(digits,str); str.deleteCharAt(str.length()-1)//每找出一个结果后,str的长度减一,添加下一种可能; } } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |