Word Break

Czytaj s od lewej. Pierwszy fragment musi być słowem, od którego zaczyna się s. Wypróbuj każde takie słowo i dla każdego z nich zadaj to samo pytanie o pozostałe litery. Jeśli którekolwiek słowo prowadzi do pełnego podziału, odpowiedź brzmi true. Jeśli żadne — false. Gdy nic nie pozostaje, udało Ci się podzielić wszystkie litery, więc to oznacza sukces.

Ta metoda sprawdza każde możliwe pierwsze słowo, następnie każde możliwe drugie słowo i tak dalej, więc nie może przeoczyć poprawnego podziału, a każdy zwrócony przez nią wynik true oznacza, że istnieje rzeczywisty podział.

Jest powolna, ponieważ wielokrotnie sprawdza te same pozostałe fragmenty. Weź 299 kopii a, po których następuje jedno b, a jako słowa przyjmij a, aa i tak dalej, aż do dziesięciu liter a. Każdy sposób podziału liter a na bloki o długości co najwyżej dziesięciu dociera do b i tam kończy się niepowodzeniem, a takich sposobów jest ponad 10^89. Rekurencja musi wypróbować je wszystkie, zanim będzie mogła zwrócić odpowiedź false.

Wynik dla pozostałej części zależy tylko od miejsca, w którym się zaczyna, a start przyjmuje tylko n + 1 wartości. W przykładzie z literą a pozostała część zaczynająca się na indeksie 20 zostaje osiągnięta po dwóch blokach po dziesięć, po dwudziestu pojedynczych literach a i na wiele innych sposobów, a jej wynik za każdym razem to false. Zapisz wynik dla każdego początku, gdy obliczysz go po raz pierwszy, a potem odczytuj go ponownie.

Komórka pamięci podręcznej potrzebuje trzech stanów: jeszcze nieobliczona, true i false. To wyniki false mają znaczenie. Wynik true natychmiast kończy całe wyszukiwanie, więc praca powtarzana przez zwykłą rekurencję odbywa się wyłącznie w gałęziach, które kończą się niepowodzeniem.

Każdy początek jest obliczany raz i sprawdza każde słowo, porównując do L liter, więc czas działania wynosi O(n × m × L): w tym przypadku najwyżej 300 × 1000 × 20 = 6 × 10^6 porównań liter. Pamięć podręczna i stos wywołań zajmują O(n) miejsca, a wywołania zagnieżdżają się na głębokość najwyżej 300.

Odwróć podejście i zajmij się prefiksami. Niech canEnd[i] określa, czy pierwsze i liter można podzielić na słowa. Pusty prefiks nie wymaga żadnych słów, więc canEnd[0] ma wartość true. Pierwsze end liter można podzielić dokładnie wtedy, gdy ich ostatni fragment — litery od start do end — jest słowem, a litery przed nim można podzielić, czyli canEnd[start] ma wartość true. Wypełniaj tablicę od lewej do prawej, a każde potrzebne canEnd[start] będzie już znane.

Zamiast porównywać wszystkie m słów w każdej pozycji, umieść słowa w zbiorze haszującym i sprawdzaj możliwe ostatnie fragmenty. Żadne słowo nie jest dłuższe niż L, więc pasować może tylko L fragmentów kończących się na end. Dla sunflowerseed wartość canEnd staje się prawdziwa w pozycjach 0, 3 (sun), 7 (flow), 9 (flower) i 13 (seed po pozycji 9), więc odpowiedź to true. Pozycja 7 donikąd nie prowadzi, ponieważ żadne słowo nie zaczyna się od er, ale tablica nie musi się tym przejmować.

Jest n pozycji, dla każdej sprawdzanych jest najwyżej L fragmentów, a utworzenie i zahaszowanie fragmentu kosztuje do L kroków. Daje to O(n × L²), czyli najwyżej 300 × 20 × 20 = 1.2 × 10^5 kroków przetwarzania liter, niezależnie od wielkości słownika. Zbudowanie zbioru wymaga jednokrotnego odczytania każdego słowa, czyli O(m × L), zatem łączna złożoność wynosi O(m × L + n × L²). Zbiór przechowuje słowa, czyli O(m × L) liter, a tablica — n + 1 wartości logicznych. Nie ma rekurencji.