Лучший способ определить, содержит ли строка несколько слов

Ответ 1

Вы можете использовать массив:

String[] matches = new String[] {"adsf", "qwer"};

bool found = false;
for (String s : matches)
{
  if (input.contains(s))
  {
    execute();
    break;
  }
}

Это эффективный, как тот, который вы разместили, но более удобен в обслуживании. Поиск более эффективного решения звучит как микро-оптимизация, которую следует игнорировать до тех пор, пока не будет доказано, что это будет узким местом вашего кода, в любом случае с огромным набором строк решение может быть trie.

Ответ 2

Я бы создал регулярное выражение из слов:

Pattern pattern = Pattern.compile("(?=.*adsf)(?=.*qwer)");
if (pattern.matcher(input).find()) {
    execute();
}

Подробнее см. в этом ответе: fooobar.com/questions/15241/...

Ответ 3

В Java 8 вы могли бы сделать,

String[] searchFor= {"asdf", "qwer"};
String input = "asdf qwer";
public static boolean containsItemFromArray(String inputString, String[] items) {
    return Arrays.stream(input).allMatch(searchFor::contains);
}

Ответ 4

Если у вас есть много подстрок для поиска, то регулярное выражение, вероятно, не будет большой помощью, поэтому вам лучше помещать подстроки в списке, а затем повторять их и вызывать input.indexOf(substring) на каждом из них. Это возвращает индекс int, где была найдена подстрока. Если вы выбрали каждый результат (кроме -1, что означает, что подстрока не была найдена) в TreeMap (где index - это ключ, а подстрока - это значение), вы можете получить их в порядке, вызвав keys() на карте.

Map<Integer, String> substringIndices = new TreeMap<Integer, String>();
List<String> substrings = new ArrayList<String>();
substrings.add("asdf");
// etc.

for (String substring : substrings) {
  int index = input.indexOf(substring);

  if (index != -1) {
    substringIndices.put(index, substring);
  }
}

for (Integer index : substringIndices.keys()) {
  System.out.println(substringIndices.get(index));
}

Ответ 5

Используйте древовидную структуру, чтобы удерживать подстроки на код. Это устраняет необходимость

Обратите внимание, что это эффективно, только если набор игл почти постоянный. Это не является неэффективным, если есть индивидуальные дополнения или абзацы подстрок, хотя, но разные инициализации каждый раз, чтобы упорядочить много строк в древовидную структуру, определенно замедляли бы его.

StringSearcher:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;

class StringSearcher{
    private NeedleTree needles = new NeedleTree(-1);
    private boolean caseSensitive;
    private List<Integer> lengths = new ArrayList<>();
    private int maxLength;

    public StringSearcher(List<String> inputs, boolean caseSensitive){
        this.caseSensitive = caseSensitive;
        for(String input : inputs){
            if(!lengths.contains(input.length())){
                lengths.add(input.length());
            }
            NeedleTree tree = needles;
            for(int i = 0; i < input.length(); i++){
                tree = tree.child(caseSensitive ? input.codePointat(i) : Character.toLowerCase(input.codePointAt(i)));
            }
            tree.markSelfSet();
        }
        maxLength = Collections.max(legnths);
    }

    public boolean matches(String haystack){
        if(!caseSensitive){
            haystack = haystack.toLowerCase();
        }
        for(int i = 0; i < haystack.length(); i++){
            String substring = haystack.substring(i, i + maxLength); // maybe we can even skip this and use from haystack directly?
            NeedleTree tree = needles;
            for(int j = 0; j < substring.maxLength; j++){
                tree = tree.childOrNull(substring.codePointAt(j));
                if(tree == null){
                    break;
                }
                if(tree.isSelfSet()){
                    return true;
                }
            }
        }
        return false;
    }
}

NeedleTree.java:

import java.util.HashMap;
import java.util.Map;

class NeedleTree{
    private int codePoint;
    private boolean selfSet;
    private Map<Integer, NeedleTree> children = new HashMap<>();

    public NeedleTree(int codePoint){
        this.codePoint = codePoint;
    }

    public NeedleTree childOrNull(int codePoint){
        return children.get(codePoint);
    }

    public NeedleTree child(int codePoint){
        NeedleTree child = children.get(codePoint);
        if(child == null){
            child = children.put(codePoint, new NeedleTree(codePoint));
        }
        return child;
    }

    public boolean isSelfSet(){
        return selfSet;
    }

    public void markSelfSet(){
        selfSet = true;
    }
}

Ответ 6

Это классическое интервью и проблема CS.

Алгоритм Робина Карпа обычно является тем, о чем люди впервые говорят в интервью. Основная идея заключается в том, что, проходя строку, вы добавляете текущий символ в хеш. Если хеш совпадает с хешем одной из ваших строк соответствия, вы знаете, что у вас может быть совпадение. Это избавляет от необходимости сканировать туда и обратно строки совпадений. https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm

Другие типичные темы для этого вопроса интервью - рассмотреть структуру три для ускорения поиска. Если у вас большой набор совпадающих строк, вы всегда должны проверять большой набор совпадающих строк. Структура Trie более эффективна для этой проверки. https://en.wikipedia.org/wiki/Trie

Дополнительные алгоритмы: - Aho – Corasick https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm - Commentz-Walter https://en.wikipedia.org/wiki/Commentz-Walter_algorithm

Ответ 7

Я думаю, что лучший подход был бы что-то вроде этого, где мы можем добавить несколько значений в одну строку и по индексу функции валидации индекса

String s = "123"; 
System.out.println(s.indexOf("1")); // 0
System.out.println(s.indexOf("2")); // 1 
System.out.println(s.indexOf("5")); // -1