We have been given a list of strings which are blacklisted. The goal is to identify if a given text contains any of these blacklisted strings. The restriction here is that the blacklisted string needs to match on the word boundary e.g. consider a blacklist string "abc" and text "abc pqr", the text in this case is unsafe (i.e. it contains a blacklisted string). On the other hand if the text is "abcoqr", then the text is safe since the string "abc" is not on the word boundary. Also the relative ordering of words in a blacklisted string needs to be checked e.g. if a blacklisted string is "abc pqr", then the text "pqr abc" is safe since the ordering of the words in the text does not match that of the blacklisted string.
Here is my solution using a modified Trie data structure. https://gist.github.com/hgadre/d4e9ec576932167f01fd33970002a882
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class SafeText {
static class Tuple {
int span = 0; // the length of previous words which should have been matched if end = true.
boolean end; // marks the identification of a blacklisted string.
Set<String> nextWords = new HashSet<>(); // next set of words to search for matching blacklisted strings.
public void setEnd(boolean end, int span) {
this.span = span;
this.end = end;
}
public boolean isEnd(int span) {
return end && span == this.span;
}
public void addNextWord (String word) {
this.nextWords.add(word);
}
public boolean containsWord(String word) {
return this.nextWords.contains(word);
}
}
private final Map<String, Tuple> m = new HashMap<>();
public SafeText(List<String> blackList) {
Collections.sort(blackList);
for (String str : blackList) {
String[] tokens = str.split("\\s");
int i = 0;
for (; i < tokens.length - 1; i++) {
m.computeIfAbsent(tokens[i], x -> new Tuple()).addNextWord(tokens[i+1]);
}
m.computeIfAbsent(tokens[i], x -> new Tuple()).setEnd(true, tokens.length-1);
}
}
public boolean isSafe(String text) {
String[] tokens = text.split("\\s");
for (int i = 0; i < tokens.length; i++) {
String key = tokens[i];
int j = i;
while (j < tokens.length && m.containsKey(key)) {
Tuple t = m.get(key);
if (t.isEnd(j-i)) {
return false;
} else if ((j+1) < tokens.length && t.containsWord(tokens[j+1])) {
key = tokens[j+1];
j++;
} else {
break;
}
}
}
return true;
}
}
Is this an optimal solution? Or is there any better approach to solve this problem?