Если слово состоит из двух допустимых слов

Question

По заданному словарю выяснить, может ли данное слово быть составлено двумя словами в словаре. Например, По данной «газете» нужно выяснить, можно ли это сделать двумя словами. (новости и бумага в этом случае). Единственное, о чем я могу думать, это начать с начала и проверить, является ли текущая строка словом. В этом случае проверка n, ne, new, news ..... проверяет оставшуюся часть, если текущая строка является допустимым словом.

Кроме того, как вы обобщаете это для k (означает, что слово состоит из k слов)? Есть мысли?

Answer 1

Начало вашего сплита в центре может дать результаты быстрее. Например, для газеты вы сначала попытаетесь разделиться на «газету новостей» или «газеты в апер». Как вы видите, для этого примера вы найдете свой результат с первой или второй попытки. Если вы не нашли результат, просто искать снаружи. Смотрите пример для арбалета ниже:

cros sbow
cro ssbow
cross bow

Answer 2

Для случая с двумя словами проблему можно решить, просто рассмотрев все возможные способы разбиения слова на два, а затем проверив каждую половину, чтобы убедиться, что это правильное слово. Если входная строка имеет длину n, то существует только O (n) различных способов разбиения строки. Если вы храните строки в структуре, поддерживающей быстрый поиск (например, три или хеш-таблицу).

Более интересный случай, когда у вас есть k> 2 слова, на которые можно разбить слово. Для этого мы можем использовать действительно элегантную рекурсивную формулировку:

Слово может быть разбито на k слов, если оно может быть разбито на слово, за которым следует слово, разбиваемое на k - 1 слово.

Рекурсивный базовый случай мог бы состоять в том, что слово можно разбить на нулевые слова, только если это пустая строка, что тривиально верно.

Чтобы использовать это рекурсивное понимание, мы изменим исходный алгоритм, рассмотрев все возможные разбиения слова на две части. После того, как у нас есть это разделение, мы можем проверить, является ли первая часть разбиения словом, и можно ли разбить вторую часть разбиения на k - 1 слово. В качестве оптимизации мы используем не все возможные разбиения, а только те, в которых мы знаем, что первое слово действительно. Вот пример кода, написанного на Java:

 public static boolean isSplittable(String word, int k, Set<String> dictionary) {
     /* Base case: If the string is empty, we can only split into k words and vice-
      * versa.
      */
     if (word.isEmpty() || k == 0)
         return word.isEmpty() && k == 0;

     /* Generate all possible non-empty splits of the word into two parts, recursing on
      * problems where the first word is known to be valid.
      *
      * This loop is structured so that we always try pulling off at least one letter
      * from the input string so that we don't try splitting the word into k pieces
      * of which some are empty.
      */
     for (int i = 1; i <= word.length(); ++i) {
          String first = word.substring(0, i), last = word.substring(i);

          if (dictionary.contains(first) &&
              isSplittable(last, k - 1, dictionary)
              return true;
     }

     /* If we're here, then no possible split works in this case and we should signal
      * that no solution exists.
      */
     return false;
 }

 }

Этот код в худшем случае выполняется за время O (n ^k ), потому что он пытается сгенерировать все возможные разбиения строки на k различных частей. Конечно, вряд ли удастся поразить это наихудшее поведение, потому что большинство возможных расщеплений не приведут к формированию каких-либо слов.

Answer 3

Я бы сначала перебрал словарь, используя функцию strpos (-like), чтобы проверить, происходит ли это вообще.Затем попробуйте найти совпадение с результатами.Таким образом, он будет делать что-то вроде этого:

• Проходить по словарю, помещая каждое слово в словарь и сохраняя результаты в массив, скажем, он дает мне результаты 'new', 'paper'и 'новости'.
• Проверьте, если новая + бумага == газета, проверьте, если новая + новости == газета и т. д., пока вы не доберетесь до бумаги + новости == газета, которая возвращается.

Не уверен, что это хороший метод, но он кажется более эффективным, чем проверка слова буква на букву (больше итераций), и вы не объяснили, как вы проверите, когда начинается второе слово.

Не знаю, что вы подразумеваете под «как вы обобщаете это для k».