题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 示例: 输入：“23” 输出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

回溯+递归

class Solution { public List<String> letterCombinations(String digits) { List<String> res = new ArrayList<>(); if(digits == null || digits.length() <1) return res; Map<Character,String> hashmap = new HashMap<>(); hashmap.put('2',"abc"); hashmap.put('3',"def"); hashmap.put('4',"ghi"); hashmap.put('5',"jkl"); hashmap.put('6',"mno"); hashmap.put('7',"pqrs"); hashmap.put('8',"tuv"); hashmap.put('9',"wxyz"); StringBuffer sb = new StringBuffer(); Deque<String> chars = new ArrayDeque<>(); for(char c:digits.toCharArray()){ String add = hashmap.get(c); chars.addLast(add); } getRes(res,chars,sb,digits.length()); return res; } public static void getRes( List<String> res,Deque<String> chars, StringBuffer sb, int len1) { if(chars.isEmpty()){ if(len1 == sb.length()) res.add(sb.toString()); }else{ String firstChars = chars.getFirst(); int len =firstChars.length(); chars.removeFirst(); for(int i=0;i<len;i++){ sb.append(firstChars.charAt(i)); getRes(res,chars,sb,len1); sb.deleteCharAt(sb.length()-1); } chars.addFirst(firstChars); } } }