GuilinDev
Lc0017
05 August 2008
17 - Letter Combinations of a Phone Number
原题概述
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.
Example:
1
2
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.
题意和分析
求电话号码的字母组合，即数字2到9中每个数字可以代表按键上的数个字母，输入是一串数字，求出所有可能的组合，最后返回的结果的顺序不重要。类似题目有90 - Subsets II, 113 - Path Sum II, 46 - Permutations, 47 - Permutionas II, 77 - Combinations, 39 - Combination Sum, 40 Combination Sum II等。
这道题是经典的 backtracking回溯算法，
当一个题目，存在各种满足条件的组合，并且需要把它们全部列出来，就可以考虑backtracking了，不过注意，backtracking一定程度上属于穷举，当数据特别大的时候吧不合适，这时通常应该考虑DP。
先创建一个mapping，对应所有的键，比如输入”23”，2对应”abc”，3对应”def”，在递归的时候先确定2对应的字母之一，比如a，然后按照回溯模板的做法来即可。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
// 类变量，也可以把这些作为参数参数helper function
List<String> results;
StringBuilder oneResult;
String[] buttons;
public List<String> letterCombinations(String digits) {
results = new ArrayList<>();
if (digits.isEmpty()) { // corner cases
return results;
}
oneResult = new StringBuilder();
// 方便查找字符
buttons = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
dfs(0, digits);
return results;
}
private void dfs(int curLen, String digits) {
if (oneResult.length() == digits.length()) {
results.add(oneResult.toString());
return;
}
for (char ch : buttons[digits.charAt(curLen) - '0'].toCharArray()) { //遍历根据输入数字找到的某个字符串的所有字符
oneResult.append(ch);
dfs(curLen + 1, digits);
//回溯
oneResult.deleteCharAt(oneResult.length() - 1);
}
}
}
没有类变量，正常的回溯写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public List<String> letterCombinations(String digits) {
List<String> results = new ArrayList<>();
if (digits.isEmpty()) { // corner cases
return results;
}
// 方便查找字符
String[] buttons = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
StringBuilder oneResult = new StringBuilder();
dfs(digits, buttons, results, oneResult, 0);
return results;
}
private void dfs(String digits, String[] buttons, List<String> results, StringBuilder oneResult, int curLen) {
if (oneResult.length() == digits.length()) {
results.add(oneResult.toString());
return;
}
for (char ch : buttons[digits.charAt(curLen) - '0'].toCharArray()) { //遍历根据输入数字找到的某个字符串的所有字符
oneResult.append(ch);
dfs(digits, buttons, results, oneResult, curLen + 1);
//回溯
oneResult.deleteCharAt(oneResult.length() - 1);
}
}
}
迭代的办法则可以用BFS或者DFS来做，下面是BFS是使用队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public List<String> letterCombinations(String digits) {
LinkedList<String> result = new LinkedList<>();//创建一个queue
if (digits.isEmpty()) {
return result;
}
String[] mapping = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
result.add("");
while (result.peek().length() < digits.length()) {//如果队列中的字符串的长度还小与input digits的长度，就继续BFS
String shorterStr = result.remove(); // 从队列中弹出长度还未到达结果长度的临时字符串元素
char ch = digits.charAt(shorterStr.length());//e.g.,比如给定的例子中树形结构的第二层有三个元素，分别是a，b，c，这时候长度还不满足最后条件，继续做BFS到树形结构下一层
String map = mapping[ch - '0'];//该层的所有元素
for (char temp : map.toCharArray()) {//该层的所有元素分别加入一个字符成为下一层的树形结构节点
result.addLast(shorterStr + temp);
}
}
return result;
}
}