Word Alert – AlgoBox by dietpepsi
Given an infinite stream of characters and a list of strings
Example:
Note that
Read full article from Word Alert – AlgoBox by dietpepsi
Given an infinite stream of characters and a list of strings
words, create a function that call an external api alert() when a word in d is recognized during the processing of the stream.Example:
words = ["ok", "test", "one", "try", "trying"]stream = "abcokdeftrying..........."alert() is called three times (k, y and g).Note that
alert() is called once at most for each character in the stream.Not efficient:
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
|
public void insert(String s) {
TrieNode node = this.root;
char[] chArr = s.toCharArray();
for (char ch : chArr) {
if (!node.children.containsKey(ch)) node.children.put(ch, new TrieNode(ch));
node = node.children.get(ch);
}
node.isString = true;
}
public int search(String stream) {
int times = 0;
char[] seq = stream.toCharArray();
TrieNode node = root;
for (char ch : seq) {
if (!node.children.containsKey(ch)) {
node = root;
if (!node.children.containsKey(ch)) continue;
else node = node.children.get(ch);
} else {
node = node.children.get(ch);
if (node.isString) times++;
}
}
return times;
}
}
public static class TrieNode {
char ch;
boolean isString;
HashMap<Character, TrieNode> children;
public TrieNode(char c) {
this.ch = c;
this.children = new HashMap<>();
this.isString = false;
}
}
|
