0

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

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;
        }
    }
}
4

3 回答 3

1

考虑Java 8版本的 @Mad Physicist 实现：

        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));
于 2019-07-03T13:49:35.617 回答
0

如果您想检查连续字符的每个可能组合，那么您的算法是O(n^2)，假设您使用Set具有O(1)查找特征的 a ，例如 a HashSet。您可能可以通过将数据和黑名单分解为 Trie 结构并以这种方式遍历每种可能性来减少这种情况。

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

isProfane = false;
for(String word: phrase.toLowerCase().split("\\s+")) {
    if(blacklistPhraseSet.contains(word)) {
        isProfane = true;
        break;
    }
}
于 2019-07-03T12:25:01.860 回答
0

您不会在时间复杂度上提高很多，因为它们在后台使用迭代，但是您可以将短语拆分为空格并迭代短语中的单词数组。就像是：

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

这段代码的问题是，除非你的单词包含复合词，否则它不会匹配那些，而我理解的你的代码会。黑名单中的单词“f**k”与我的代码中的“f**kwit”不匹配，它会出现在你的代码中。

于 2019-07-03T12:49:15.637 回答