745 Prefix and Suffix Search

1. Question

Given manywords,words[i]has weighti.
Design a classWordFilterthat supports one function,WordFilter.f(String prefix, String suffix). It will return the word with givenprefixandsuffixwith maximum weight. If no word exists, return -1.
Examples:
1
Input:
2
3
WordFilter(["apple"])
4
WordFilter.f("a", "e") // returns 0
5
WordFilter.f("b", "") // returns -1
Copied!
Note:
  1. 1.
    wordshas length in range[1, 15000].
  2. 2.
    For each test case, up towords.lengthqueriesWordFilter.fmay be made.
  3. 3.
    words[i]has length in range[1, 10].
  4. 4.
    prefix, suffixhave lengths in range[0, 10].
  5. 5.
    words[i]andprefix, suffixqueries consist of lowercase letters only.

2. Implementation

(1) HashMap
1
class WordFilter {
2
Map<String, Integer> map;
3
4
public WordFilter(String[] words) {
5
map = new HashMap<>();
6
7
for (int i = 0; i < words.length; i++) {
8
String curWord = words[i];
9
List<String> prefix = new ArrayList<>();
10
List<String> suffix = new ArrayList<>();
11
12
for (int j = 0; j <= curWord.length(); j++) {
13
prefix.add(curWord.substring(0, j));
14
}
15
16
for (int k = curWord.length(); k >= 0; k--) {
17
suffix.add(curWord.substring(k));
18
}
19
20
for (String p : prefix) {
21
for (String s : suffix) {
22
String key = p + "#" + s;
23
if (!map.containsKey(key)) {
24
map.put(key, i);
25
}
26
else {
27
map.put(key, Math.max(map.get(key), i));
28
}
29
}
30
}
31
}
32
}
33
34
public int f(String prefix, String suffix) {
35
return map.containsKey(prefix + "#" + suffix) ? map.get(prefix + "#" + suffix) : -1;
36
}
37
}
38
39
/**
40
* Your WordFilter object will be instantiated and called as such:
41
* WordFilter obj = new WordFilter(words);
42
* int param_1 = obj.f(prefix,suffix);
43
*/
Copied!
(2) Trie
思路: 利用trie的特性,将suffix + "#" + prefix作为key插入trie里,并以此作为查询的key
1
class WordFilter {
2
class TrieNode {
3
int weight;
4
boolean isWord;
5
TrieNode[] childNode;
6
7
public TrieNode() {
8
weight = -1;
9
childNode = new TrieNode[256];
10
}
11
}
12
13
class Trie {
14
TrieNode root;
15
16
public Trie() {
17
root = new TrieNode();
18
}
19
20
public void insert(String word, int weight) {
21
if (word == null || word.length() == 0) {
22
return;
23
}
24
25
TrieNode curNode = root;
26
27
for (char c : word.toCharArray()) {
28
int index = c;
29
if (curNode.childNode[index] == null) {
30
curNode.childNode[index] = new TrieNode();
31
}
32
curNode = curNode.childNode[index];
33
curNode.weight = weight;
34
}
35
curNode.isWord = true;
36
}
37
38
public TrieNode search(String word) {
39
if (word == null || word.length() == 0) {
40
return null;
41
}
42
43
TrieNode curNode = root;
44
45
for (char c : word.toCharArray()) {
46
int index = c;
47
if (curNode.childNode[index] == null) {
48
return null;
49
}
50
curNode = curNode.childNode[index];
51
}
52
return curNode;
53
}
54
55
public int getWeight(String word) {
56
TrieNode node = search(word);
57
return node == null ? -1 : node.weight;
58
}
59
}
60
61
Trie trie;
62
public WordFilter(String[] words) {
63
trie = new Trie();
64
65
for (int i = 0; i < words.length; i++) {
66
String curWord = words[i];
67
String key = "#" + curWord;
68
trie.insert(key, i);
69
70
for (int j = curWord.length() - 1; j >= 0; j--) {
71
key = curWord.charAt(j) + key;
72
trie.insert(key, i);
73
}
74
}
75
}
76
77
public int f(String prefix, String suffix) {
78
return trie.getWeight(suffix + "#" + prefix);
79
}
80
}
81
82
/**
83
* Your WordFilter object will be instantiated and called as such:
84
* WordFilter obj = new WordFilter(words);
85
* int param_1 = obj.f(prefix,suffix);
86
*/
Copied!

3. Time & Space Complexity

HashMap: 时间复杂度O(nl^2), n是word的个数, l是word的平均长度, 空间复杂度O(nl^2)
Trie: 时间复杂度O(nl^2), n是word的个数, l是word的平均长度, 空间复杂度O(nl^2)