Эффективная альтернатива вложенному For Loop

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

Вы не сильно улучшите временную сложность, потому что они используют итерации под капотом, но вы можете разбить фразу на пробелы и перебрать массив слов из вашей фразы. Что-то вроде:

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

Проблема этого кода в том, что если ваше слово не содержит составных слов, оно не будет соответствовать этим, тогда как ваш код, как я понимаю, будет. Слово "f ** k" в черном списке не будет совпадать с "f ** kwit" в моем коде, оно будет в вашем.

Answer 2

Рассмотрим 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));

Answer 3

Если вы хотите проверить каждую возможную комбинацию последовательных символов, тогда ваш алгоритм - O(n^2), при условии, что вы используете Set с O(1) характеристиками поиска, такими как HashSet.Вы, вероятно, сможете уменьшить это, разбив данные и черный список на структуры Trie и пройдя по каждой возможности таким образом.граница слова ".Тогда вы можете сделать

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