top17
给一串数字，每个数可以代表数字键下的几个字母，返回这些数字下的字母的所有组成可能。
解法一 定义相乘
自己想了用迭代，用递归，都理不清楚，灵机一动，想出了这个算法。
把字符串 "23" 看成 ["a","b",c] * ["d","e","f"] ，而相乘就用两个 for 循环实现即可，看代码应该就明白了。
publicList<String>letterCombinations(Stringdigits) { List<String>ans=newArrayList<String>(); for (inti=0; i<digits.length(); i++) { ans=mul(ans, getList(digits.charAt(i) -'0')); } returnans; } publicList<String>getList(intdigit) { StringdigitLetter[] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; List<String>ans=newArrayList<String>(); for (inti=0; i<digitLetter[digit].length(); i++) { ans.add(digitLetter[digit].charAt(i) +""); } returnans; } //定义成两个 List 相乘publicList<String>mul(List<String>l1, List<String>l2) { if (l1.size() !=0&&l2.size() ==0) { returnl1; } if (l1.size() ==0&&l2.size() !=0) { returnl2; } List<String>ans=newArrayList<String>(); for (inti=0; i<l1.size(); i++) for (intj=0; j<l2.size(); j++) { ans.add(l1.get(i) +l2.get(j)); } returnans; }
解法二 队列迭代
参考这里，果然有人用迭代写了出来。主要用到了队列。
publicList<String>letterCombinations(Stringdigits) { LinkedList<String>ans=newLinkedList<String>(); if(digits.isEmpty()) returnans; String[] mapping=newString[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; ans.add(""); for(inti=0; i<digits.length();i++){ intx=Character.getNumericValue(digits.charAt(i)); while(ans.peek().length()==i){ //查看队首元素Stringt=ans.remove(); //队首元素出队for(chars : mapping[x].toCharArray()) ans.add(t+s); } } returnans; }
假如是 "23" ，那么
第 1 次 for 循环结束后变为 a, b, c；
第 2 次 for 循环的第 1 次 while 循环 a 出队，分别加上 d e f 然后入队，就变成 b c ad ae af
第 2 次 for 循环的第 2 次 while 循环 b 出队，分别加上 d e f 然后入队，就变成 c ad ae af bd be bf
第 2 次 for 循环的第 3 次 while 循环 c 出队，分别加上 d e f 然后入队，就变成 ad ae af bd be bf cd ce cf
这样的话队列的元素长度再也没有等于 1 的了就出了 while 循环。
总
这种题的时间复杂度和空间复杂度自己理的不太清楚就没有写了。
