Разбиение строки на слова
Урок 14 из 14 курса Префиксные деревья (Trie) — Серия «Структуры данных» №8 на Coddy.
Дана строка s и словарь слов. Можно ли разбить s на последовательность словарных слов без остатка? "leetcode" разбивается на "leet" + "code", если оба слова есть в словаре; "catsandog" не разбивается, как бы мы его ни резали.
Проход динамическим программированием решает эту задачу. Определим dp[i] как можно ли сегментировать первые i символов? Начнем с dp[0] = true. Для каждого i, где dp[i] равно true, пройдите по префиксному дереву (trie), начиная с позиции i в строке; каждый раз, когда обход попадает в узел isEndOfWord на индексе j, установите dp[j+1] = true.
Префиксное дерево ускоряет каждый обход: отсутствие одного символа завершает его. Окончательный ответ находится в dp[n].
Задание
СреднеНапишите функцию wordBreak, которая принимает строку s и массив строк dictionary и возвращает true, если s можно разбить на одну или несколько частей без пробелов, которые присутствуют в словаре, или false в противном случае.
Пустая строка s всегда может быть разбита.
Вы должны использовать класс Trie (предоставленный в trie вместе с trienode) — не используйте встроенные средства языка, такие как множества (sets), словари (dicts) или карты (maps) для подсчета или отслеживания.
Попробуйте сами
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "solution.h"
int main() {
char s[4096], dLine[4096];
if (!fgets(s, sizeof(s), stdin)) s[0] = 0;
if (!fgets(dLine, sizeof(dLine), stdin)) dLine[0] = 0;
s[strcspn(s, "\r\n")] = '\0';
dLine[strcspn(dLine, "\r\n")] = '\0';
char* d[1024]; int dn = 0;
char* tok = strtok(dLine, " \t");
while (tok && dn < 1024) { d[dn++] = tok; tok = strtok(NULL, " \t"); }
printf("%s\n", wordBreak(s, d, dn) ? "true" : "false");
return 0;
}
Все уроки раздела Префиксные деревья (Trie) — Серия «Структуры данных» №8
3Практические задачи
Самый длинный общий префиксПодсчет слов с префиксомАвтодополнениеСамое длинное слово в словареРазбиение строки на слова