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.
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.
Tags: String, Backtracking
题意是给你按键，让你组合出所有不同结果，首先想到的肯定是回溯了，对每个按键的所有情况进行回溯，回溯的终点就是结果字符串长度和按键长度相同。
classSolution { privatestaticString[] map = newString[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; publicList<String> letterCombinations(Stringdigits) { if (digits.length() == 0) returnCollections.emptyList(); List<String> list = newArrayList<>(); helper(list, digits, ""); returnlist; } privatevoidhelper(List<String> list, Stringdigits, Stringans) { if (ans.length() == digits.length()) { list.add(ans); return; } for (charc : map[digits.charAt(ans.length()) - '2'].toCharArray()) { helper(list, digits, ans + c); } } }还有一种思路就是利用队列，根据上一次队列中的值，该值拼接当前可选值来不断迭代其结果，具体代码如下。
classSolution { privatestaticString[] map = newString[]{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; publicList<String> letterCombinations(Stringdigits) { if (digits.length() == 0) returnCollections.emptyList(); LinkedList<String> list = newLinkedList<>(); list.add(""); char[] charArray = digits.toCharArray(); for (inti = 0; i < charArray.length; i++) { charc = charArray[i]; while (list.getFirst().length() == i) { Stringpop = list.removeFirst(); for (charv : map[c - '2'].toCharArray()) { list.addLast(pop + v); } } } returnlist; } }如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：awesome-java-leetcode
