T9: On old cell phones, users typed on a numeric keypad and the phone would provide a list of words that matched these numbers. Each digit mapped to a set of 0 - 4 letters. Implement an algorithm to return a list of matching words, given a sequence of digits. You are provided a list of valid words (provided in whatever data structure you’d like). The mapping is shown in the diagram below:
1
2
3
4
5
6
7
8
9
10
11
12
|
|-----|-----|-----|
| 1 | 2 | 3 |
| | abc | def |
|-----|-----|-----|
| 4 | 5 | 6 |
| ghi | jkl | mno |
|-----|-----|-----|
| 7 | 8 | 9 |
|pqrs | tuv | wxyz|
|-----|-----|-----|
| | 0 | |
|-----|-----|-----|
|
Example：
1
2
3
|
Input : 8733
Output : tree, used
Hints : #477, #487, #654, #703, #726, #744
|
解法1
把数字所能组成的word统统算出来，然后按个看是否在字典里。
算法则是：
1
2
3
4
5
|
allWords(digits[0~n]) = allChars of digits[0] * allWords(digits[1~n])
allWords(digits[0~n]): 数字序列所可能组成的所有单词
allChars of digits[0]: 第一个数字的所有可能字符
allWords(digits[1~n]): 数字序列（去掉第一个数字）所可能组成的所有单词
|
代码：
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
31
32
33
34
35
36
37
|
Map<Integer, String[]> digitMap = new HashMap<>();
digitMap.put(1, new String[] {""});
digitMap.put(2, new String[] {"a", "b", "c"});
digitMap.put(3, new String[] {"d", "e", "f"});
//...
digitMap.put(0, new String[] {""});
Set<String> dictionary = new HashSet<>();
/// 初始化字典数据
public List<String> allValidWords(int[] digits) {
List<String> allWords = allWords(digits);
List<String> result = new ArrayList<>();
for (String word : allWords) {
if (dictionary.contains(word)) {
result.add(word);
}
}
return result;
}
private List<String> allWords(int[] digits) {
if (digits.length == 1) {
return digitMap.get(digits[0]);
}
int[] subDigits = Arrays.subArray(digits, 1); // 截取digits[1~tail]
List<String> subAllWords = allWords(subDigits);
List<String> result = new ArrayList<>();
char[] firstChars = digitMap.get(digits[0]);
for (int i = 0; i < firstChars.length; i++) {
for (String subWord : subAllWords) {
result.add(firstChars[i] + subWord);
}
}
return result;
}
|
时间复杂度：O(3n)，n代表数字位数，3是因为大部分数字只代表3个字符，所以取3。
解法2
解法1时间太长了，是否可以在遍历所有可能性的过程中就去掉可能存在的结果呢？比如8733有一种可能是tqdd，那么在q的时候就能够知道不存在以tq开头的单词，那么后面的就不需要再比较了。
那么我们把Dictionary做成一种树形的结构，比如：
1
2
3
4
5
6
7
8
9
10
11
|
t
/ \
r a
/ \ |
e a i
/ | |
e i l
| l |
. | .
.
.代表结束
|
代码：
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
|
public class WordNode {
Map<Char, WordNode> next;
}
Map<Integer, char[]> digitMap = new HashMap<>();
public List<String> allValidWords(int[] digits) {
List<String> result = new ArrayList<>();
WordNode root = ...;
searchWord(digits, 0, root, "", result);
return result;
}
private void searchWord(int[] digit, int index, WordNode node, String word, List<String> result) {
if (index == digit.length && node.isEnd()) {
// digit走到底，且单词结束
result.add(word);
return;
}
char[] chars = digitMap.get(digit[index]);
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (node.containsNext(c)) {
searchWord(digit, index + 1, node.next(c), word + c, result);
}
}
}
|
时间复杂度：最坏情况是O(3n)，n是digits的长度，当比如你弄了一个8733，但是字典里的单词长度都大于4，且每个word的前缀都是8733所能构成的字符串。
解法3
换个角度思考，可以先将字典中的所有word都转成数字形式，然后构建一个digits -> word list的表。
代码：
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
// 构建 digits -> word list
public Map<String, List<String>> makeDigits2Words(List<String> dictionary) {
Map<String, List<String>> result = new HashMap<>();
for (String word : dictionary) {
String digits = toDigits(word);
List<String> words = result.get(digits);
if (words == null) {
words = new ArrayList<>();
result.put(digits, words);
}
words.add(word);
}
return result;
}
private String toDigits(String word) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(c);
char d = toDigit(c);
sb.append(d);
}
return sb.toString();
}
private char toDigit(char c) {
if ('a' <= c && c <= 'c') {
return '2';
}
if ('d' <= c && c <= 'f') {
return '3';
}
if ('g' <= c && c <= 'i') {
return '4';
}
...
}
private Map<String, List<String>> digitWords = makeDigits2Words(dictionary);
public List<String> allValidWords(String digits) {
return digitWords.get(digits);
}
|
时间复杂度：在于makeDigits2Words方法，这个方法实际上遍历了dictionary所有word的所有字符，所以复杂度为O(N)，N为字典中的所有word的长度之和。
评论