Блог

Главная - Вопросы по программированию - Эффективная проверка, содержит ли строка набор слов

Эффективная проверка, содержит ли строка набор слов

#java

#java

Вопрос:

Допустим, у меня есть несколько наборов слов, таких как: (вода, мука, яйца) и (бобы, вода, молоко)

Если пользователь вводит строку, содержащую все эти слова в любом порядке, отображается сообщение. Например, «У меня есть яйца, вода и немного муки» -> «Из этого получается пирог».

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

Моя первоначальная идея — использовать .contains:

 for(each-word-set)
{
  i = word-set.length;
  for(each-word)
  {
    if(string.contains(word))
    {
       j  
    }
  }
  if(i == j)
  {
     //Yes this string contains all words.
  }
}

Есть ли лучший метод, чем этот?

Комментарии:

1. Загляните в aho-corasick.

2. Я еще не уверен, я предполагаю, что hashmap?

3. Содержит ли строка, вводимая пользователем, какие-либо разделители? Например, мука, бобы и т.д.?

4. Пробелы между каждым словом будут действовать как разделители.

5. Вам следует подумать if(string.contains(word)){j }else{break;} … Завершает цикл, если цель недостижима. Как следствие, вы можете удалить тест i==j . Если вы достигнете этой точки, все всегда будет в порядке.

Ответ №1:

Мой первоначальный способ: использование пробела в качестве разделителя.

Мы можем сделать следующее.

Шаги

Создайте список. Следующим образом

1) Используйте функцию разделения Java. Для создания массива.

  List<String> list = new ArrayList<String>(Arrays.asList(string.split(" ")))`;

2) Создайте хэш-карту.

 Map<String, String> hash = new HashMap<String, String>();    
for(i = 0 ; i < list.length(); i  )
{
   hash.put(list[i], list[i]);
}

Где list[i] будет вашим ключом.

3) Извлеките совпадения.

Теперь, когда пользователь вводит слово, которое вас интересует, вы можете использовать команду containsKey
. Например 

   if (hash.containsKey("flour") amp;amp; hash.containsKey("water") amp;amp; hash.containsKey("beans");

  println("Whatever you want");

Следует отметить, что создание хэш-таблицы полезно для больших наборов данных. Вот ссылка, вы должны посмотреть, чтобы увидеть преимущества. Извлечение данных из хэш-таблицы составляет O (1), поэтому выполняется практически мгновенно.

Надеюсь, это было полезно.

Ответ №2:

Чтобы дополнить мой комментарий. Было допущено еще несколько ошибок. Мое окончательное решение на данный момент было бы:

 public class Someclass {
    public static void main(String[] args) {

        String[] words = { "water", "flour", "eggs", "beans", "water", "milk" };
        String[] testStrings = { "water flour eggs beans water milk", "somewhat else",
                        "wader flour ekks beans water milk" };
        for (String string : testStrings) {
            boolean found = true;
            for (String word : words) {
                if (!string.contains(word)) {
                    found = false;
                    break;
                }
            }
            if (found) {
                System.out.println(string   " - That makes a cake");
            } else {
                System.out.println(string   " - That makes no cake");
            }
        }
    }
}

Ответ №3:

 You can first create an array or list of strings splitted by space as:

List<string>userStr= userEntry.split(" ");

Now use extended for loop within another loop as:

for(String s: userStr)
{
    for(String d: yourList){
       if(s.equals d){
          //your code 
           break;
        }
     }
}