3
\$\begingroup\$

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?

|improve this question
\$\endgroup\$
  • \$\begingroup\$ I don't see any kind of trie involved in your code. \$\endgroup\$ – 200_success Dec 14 '18 at 18:59
  • \$\begingroup\$ @200_success its a modified trie. I am storing a mapping between a given word and the set of words which can occur in one or more blacklisted strings. e.g. if blacklisted string is "a b" then the mapping would be : a -> {false, 0, [b]} and b -> {true, 2, []}. make sense? \$\endgroup\$ – hsg Dec 14 '18 at 19:44
1
\$\begingroup\$

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;
  }
}
|improve this answer
\$\endgroup\$
  • \$\begingroup\$ I was about to post a very similar solution :) \$\endgroup\$ – Ronan Dhellemmes Dec 18 '18 at 16:22
  • \$\begingroup\$ No this will not work when the blacklisted string contains multiple words and we need to make sure that the all these words match in the text (in the correct order). In your solution, you have split the content string at the word boundary and inserted in the set. So I think you will loose the ordering amongst the individual words. For concrete examples please take a look at gist.github.com/hgadre/d4e9ec576932167f01fd33970002a882 \$\endgroup\$ – hsg Dec 18 '18 at 18:45
  • \$\begingroup\$ Having only words in the blacklist entries must be an precondition. There was no oreding requirement in your question, that is why I said "I may have missed something". But if you want to keep the ordering you can use a List instead of Set. Please update your requirements in this question. \$\endgroup\$ – gervais.b Dec 19 '18 at 8:54
  • \$\begingroup\$ OK I updated the question now. BTW a trivial solution would be to use in-built substring match library function for every combination of (text, blacklisted_str). But this will not be very efficient when there are large number of blacklisted strings or if the size of the text is large. \$\endgroup\$ – hsg Dec 19 '18 at 19:36
  • \$\begingroup\$ Blacklisting and substrings also yields false positives. Blacklisting "sex" would claim that "Middlesex, New Jersey" is a bad phrase. \$\endgroup\$ – Rick Davin Dec 19 '18 at 20:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.