有效替代嵌套循环的替代品

Question

我正在执行亵渎过滤器。如下所示，我有2个嵌套的环。有没有更好的方法避免嵌套以进行循环并提高时间复杂性。

boolean isProfane = false;
final String phraseInLowerCase = phrase.toLowerCase();
for (int start = 0; start < phraseInLowerCase.length(); start++) {
    if (isProfane) {
        break;
    }
    for (int offset = 1; offset < (phraseInLowerCase.length() - start + 1 ); offset++) {
        String subGeneratedCode = phraseInLowerCase.substring(start, start + offset);
        //BlacklistPhraseSet is a HashSet which contains all profane words
        if (blacklistPhraseSet.contains(subGeneratedCode)) {
            isProfane=true;
            break;
        }
    }
}

Answer 1

考虑 Java 8 @mad物理学家实现的版本：

        boolean isProfane = Stream.of(phrase.split("\s+"))
            .map(String::toLowerCase)
            .anyMatch(w -> blacklistPhraseSet.contains(w));

或

        boolean isProfane = Stream.of(phrase
            .toLowerCase()
            .split("\s+"))
            .anyMatch(w -> blacklistPhraseSet.contains(w));

Answer 2

如果要检查连续字符的所有可能组合，则您的算法为 O(n^2)，假设您使用具有O(1)查找特性的Set，例如HashSet。您可能可以通过将数据和黑名单分解为Trie结构并以这种方式行走来减少这一点。

一种更简单的方法可能是使用诸如"亵渎总是在单词边界开始和结束"之类的启发式方法。那你可以做

isProfane = false;
for(String word: phrase.toLowerCase().split("\s+")) {
    if(blacklistPhraseSet.contains(word)) {
        isProfane = true;
        break;
    }
}

Answer 3

您不会在时间复杂性上提高很多，因为这些迭代在引擎盖下使用的迭代，但是您可以在空间上将短语分开，然后从短语中迭代一系列单词。类似：

String[] arrayWords = phrase.toLowerCase().split(" ");
for(String word:arrayWords){
    if(blacklistPhraseSet.contains(word)){
        isProfane = true;
        break;
    }
}

此代码的问题是，除非您的单词包含复合词，否则它与这些单词不匹配，而您的代码符合我的理解。黑色列表中的" f ** k"一词与我的代码中的" f ** kwit"不匹配，它将在您的代码中。