Dzielenie słowa
Lekcja 14 z 14 w kursie Drzewa Trie — struktury danych #8 w Coddy.
Mając ciąg znaków s i słownik słów, czy możemy podzielić s na sekwencję słów ze słownika, tak aby nic nie pozostało? Ciąg "leetcode" można podzielić na "leet" + "code", jeśli oba słowa znajdują się w słowniku; ciągu "catsandog" nie da się podzielić, niezależnie od sposobu.
Rozwiązanie zapewnia przebieg z wykorzystaniem programowania dynamicznego. Zdefiniuj dp[i] jako czy pierwsze i znaków można podzielić? Zacznij od dp[0] = true. Dla każdego i, dla którego dp[i] ma wartość true, przejdź przez trie, zaczynając od pozycji i w ciągu; za każdym razem, gdy przejście dotrze do węzła isEndOfWord na indeksie j, ustaw dp[j+1] = true.
Trie przyspiesza każde przejście: wystarczy jeden brakujący znak, aby je zakończyć. Ostateczna odpowiedź znajduje się w dp[n].
Wyzwanie
ŚredniNapisz funkcję wordBreak, która przyjmuje ciąg znaków s i tablicę ciągów znaków dictionary, a następnie zwraca true, jeśli s można podzielić na jeden lub więcej fragmentów niezawierających białych znaków, które wszystkie znajdują się w słowniku, lub w przeciwnym razie zwraca false.
Pusty ciąg s zawsze można podzielić.
Musisz użyć klasy Trie (udostępnionej w trie wraz z trienode) — nie używaj wbudowanych elementów języka, takich jak zbiory, słowniki ani mapy, do zliczania ani śledzenia.
Spróbuj swoich sił
#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;
}
Wszystkie lekcje w sekcji Drzewa Trie — struktury danych #8
3Wyzwania praktyczne
Najdłuższy wspólny prefiksPolicz słowa z danym prefiksemAutouzupełnianieNajdłuższe słowo w słownikuDzielenie słowaPoćwicz samodzielnie: Kompilator C online