17. Letter Combinations of a Phone Number(电话号码的字母组
Medium
Given a string containing digits from? A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]. Note: Although the above answer is in lexicographical order,your answer could be in any order you want. ? 方法一:递归 ? import java.util.ArrayList; import java.util.List; class Solution { public List<String> letterCombinations(String digits) { List<String> result=new ArrayList<String>(); //存结果 String[] map={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; char[]tmp=new char[digits.length()]; if(digits.length()<1) return result; rec(digits,0,tmp,map,result); return result; } private void rec(String digits,int index,char[] tmp,String[] map,List<String> result) { if(index==digits.length()){ result.add(new String(tmp)); return; } char tmpChar=digits.charAt(index); for(int i=0;i< map[tmpChar - ‘0‘].length();i++){ tmp[index]=map[tmpChar-‘0‘].charAt(i); rec(digits,index+1,result); } } } ? 方法二:回溯 ? import java.util.ArrayList; import java.util.List; class Solution { public List<String> letterCombinations(String digits) { List<String> result=new ArrayList<String>(); //存结果 String[] map={"","wxyz"}; StringBuilder tmp=new StringBuilder(); if(digits.length()<1) return result; backtrack(digits,result); return result; } private void backtrack(String digits,StringBuilder tmp,List<String> result) { if(index==digits.length()){ result.add(new String(tmp)); return; } char tmpChar=digits.charAt(index); for(int i=0;i< map[tmpChar - ‘0‘].length();i++){ tmp.append(map[tmpChar-‘0‘].charAt(i)); backtrack(digits,result); tmp.deleteCharAt(tmp.length()-1); } } } 总结: 递归是一种数据结构,是函数中调用本身来解决问题。 回溯就是通过不同的尝试来生成问题的解,有点类似于穷举,但是和穷举不同的是回溯会“剪枝”,意思就是对已经知道错误的结果没必要再枚举接下来的答案了。 回溯搜索是深度优先搜索(DFS)的一种。对于某一个搜索树来说(搜索树是起记录路径和状态判断的作用),回溯和DFS,其主要的区别是,回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |