Find out whether a given text contains any of the prohibited words

Question

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?

Answer 1

I may have missed something. But why don't you just use simple collections ?

// Naive implementation
class Text {
  public Text(String content, Set<String> blacklist) {
    this.words = new HashSet<>(Arrays.asList(content.split("\\s")));
    this.blacklist = blacklist;
  }

  public boolean isSafe() {
    for (String forbidden: this.blacklist) {
        if (this.words.contains(forbidden) ) {
            return false;
        }
    }
    return true;
  }
}