建议debug看一下,是一道好题。
public List<String> letterCombinations1(String digits) {LinkedList<String> ans = new LinkedList<String>();if(digits.isEmpty()) return ans;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;}
/* 确实巧妙啊,利用队列先进先出,将之前的字符串出队,拼接新的字符,新生成的字符串入队。
操作简单清楚,而且使用LinkedList,申请新空间方便,不会像ArrayList那样频繁扩容导致的性能低下
*/
回溯递归解决,也是个好办法,就是自己没写出来…
代码来源:
https://leetcode-/problems/letter-combinations-of-a-phone-number/solution/leetcode-17-letter-combinations-of-a-phone-number-/
private String letterMap[] = {" ", //0"",//1"abc", //2"def", //3"ghi", //4"jkl", //5"mno", //6"pqrs", //7"tuv", //8"wxyz" //9};private ArrayList<String> res;public List<String> letterCombinations1(String digits) {res = new ArrayList<>();if (digits.isEmpty()) return res;findCombination(digits,0,"");return res;}private void findCombination(String digits, int index, String s) {if (index == s.length()) {res.add(s);return;}int x = digits.charAt(index) - 48;String letter = letterMap[x];for (int i = 0; i < letter.length(); i++) {findCombination(digits,index + 1,s + letter.charAt(i));}return;}