Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
常规思路：把这道题转化为如下问题，对于指定的字符串集，每一项中任取一个字符，问有多少种组合方式？
以前用DFS做过自走迷宫的问题，这个是一样的道理，如下图所示：
第一步：圈1走第一条线，圈2走第一条线，....直到圈n走第一条线，将其路径存储
回退一步，圈n-1走第二条线,,,直到圈n走第一条线，将其路径存储
回退一步，圈n-1走第三条线，...直到圈n走第一条线，将其路劲存储
.......回退一步，当圈n-1走完所有条线后，回退到n-2，继续...
基本的算法如下所示
public void dfs(int index,List<String> ans){ if(index==n){ ans.add(road);//存储路径 return; } for(int i=0;i<circle[index].line;i++){ road+=circle[index].line[i]; dfs(index+1, ans); } } 然后用其去实现
public class Solution { public List<String> letterCombinations(String digits) { String[] arr={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//取2-9 ArrayList<String> str=new ArrayList<>();//用来存储数字对应的字符串 List<String> result=new ArrayList<>(); if(digits.length()==0){ return result; } for(int i=0;i<digits.length();i++){ int number=digits.charAt(i)-'0';//获取digits的每一个字符的数字 str.add(arr[number]);//将对应的arr字符串添加进str } char[] getstr=new char[str.size()]; dfs(str,0,getstr,result);//str为数字对应的字符串组，0为str中的第几个字符串，getstr为组合的字符数组，result为组合后的字符串集 return result; } public void dfs(ArrayList<String> str,int index,char[] getstr,List<String> result){ if(index==str.size()){ result.add(String.valueOf(getstr)); return; } for(int j=0;j<str.get(index).length();j++){ getstr[index]=str.get(index).charAt(j); dfs(str, index+1, getstr, result); } } } 再来看看大牛的代码，简直了
public List<String> letterCombinations(String digits) { LinkedList<String> ans = new LinkedList<String>(); String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; ans.add(""); for(int i =0; i<digits.length();i++){ int x = Character.getNumericValue(digits.charAt(i)); while(ans.peek().length()==i){ String t = ans.remove(); for(char s : mapping[x].toCharArray()) ans.add(t+s); } } return ans; } 我以字符串“23”来举例，如下图所示：
