嵌套 For 循环的有效替代方案

Question

我正在做脏话过滤。我嵌套了 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;
        }
    }
}

Answer 1

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

一种更简单的方法可能是使用像 "profanity always starts and ends at a word boundary" 这样的启发式方法。那么你可以做

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

Answer 2

你不会在时间复杂度上提高很多，因为它们在幕后使用迭代，但你可以在空格上拆分短语并迭代短语中的单词数组。类似于：

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

此代码的问题在于，除非您的单词包含复合词，否则它不会匹配这些词，而据我了解，您的代码会匹配。黑名单中的单词 "f**k" 与我的代码中的 "f**kwit" 不匹配，它会在你的代码中匹配。

Answer 3

考虑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));

嵌套 For 循环的有效替代方案

Efficient alternative to nested For Loop

java

for-loop

filter

profanity

nested-loops