Word Break
Otrzymujesz ciąg znaków s i listę słów wordDict. Zwróć true, jeśli możesz podzielić s na części, które wszystkie są słowami z wordDict, a w przeciwnym razie false.
Części zachowują swoją kolejność i razem wykorzystują każdą literę z s dokładnie raz. Słowo może być użyte dowolną liczbę razy, a nie musisz używać każdego słowa.
Funkcja
- sstring
- ciąg znaków do podzielenia na słowa
- wordDictstring-array
- słowa, których możesz używać, tak często, jak chcesz
- Zwracaboolean
- prawda, jeśli s można podzielić na słowa ze słownika, w przeciwnym razie fałsz
Ograniczenia
1 ≤ s.length ≤ 3001 ≤ wordDict.length ≤ 10001 ≤ wordDict[i].length ≤ 20si każde słowo zawierają wyłącznie małe litery alfabetu angielskiego.- Słowa w
wordDictsą różne.
Przykłady
- Wejście
- s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
- Wyjście
- true
- Wyjaśnienie
- Podziel to na
sun,flower,seed. Wzięcieflowposunpozostawiaer, od którego nie zaczyna się żadne słowo, więc pierwsze pasujące słowo nie zawsze jest właściwe.
- Wejście
- s = "bananaban"wordDict = ["ban", "ana"]
- Wyjście
- true
- Wyjaśnienie
ban+ana+banpokrywa ciąg znaków i używabandwa razy, co jest dozwolone.
- Wejście
- s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
- Wyjście
- false
- Wyjaśnienie
- Zarówno
pine+apple, jak ipineapplepozostawiajątart. Pasuje tam tylkotar, co pozostawia samotnet, więc żadne cięcie nie działa.
Pytanie dodatkowe
Zwróć najmniejszą liczbę słów, których może użyć prawidłowy podział, lub -1, jeśli nie można podzielić s. Co zmienia się w tabeli i czy zmienia się czas działania?
Podpowiedzi
Otwieraj je po kolei. Każda zdradza trochę więcej.
Pierwszym elementem dowolnego podziału jest słowo, które zaczyna się od
s. Gdy je wybierzesz, jakie pytanie pozostaje?To, czy można odciąć litery od danego indeksu do końca, zależy wyłącznie od tego indeksu. Jest tylko
n + 1takich pytań, więc zapamiętaj każdą odpowiedź, przede wszystkim tefalse.Niech
canEnd[i]określa, czy można podzielić pierwszeiliter, przy czymcanEnd[0] = true. WtedycanEnd[end]ma wartość true, jeśli dla pewnegocanEnd[start]wartość wynosi true, a litery odstartdoendtworzą słowo. Przechowuj słowa w zbiorze haszującym i próbuj tylko fragmentów nie dłuższych niż najdłuższe słowo.
Rozwiązanie
Wybieranie jednego słowa naraz nie działa, a próbowanie każdego podziału wymaga czasu wykładniczego. Jednak to, czy pozostałą część s można podzielić, zależy tylko od miejsca, w którym się zaczyna, więc istnieje tylko n + 1 pytań. Poniżej n to długość s, m to liczba słów, a L to długość najdłuższego słowa.
Wypróbuj każde słowo na każdej pozycji
Poprawne, ale nie kończy się na największych testach
Intuicja
Pierwszy element musi być słowem, od którego zaczyna się s. Wypróbuj każde takie słowo i zadaj to samo pytanie o pozostałe litery; pusty ciąg reszty oznacza, że każda litera została wykorzystana. Wypróbowanie każdego pierwszego słowa, a następnie każdego drugiego słowa nie pozwala pominąć żadnego prawidłowego podziału.
Sprawdza wciąż te same pozostałe ciągi. Przy 299 kopiach a, po których następuje jedno b, oraz słowach a, aa aż do dziesięciu a, ponad 10^89 sposobów podziału liter a na bloki dociera do b i kończy się niepowodzeniem, a rekurencja wypróbowuje je wszystkie.
Algorytm
- Napisz
canSplit(start): czy litery odstartdo końca można podzielić? Jeślistartjest równy długościs, zwróćtrue. - Dla każdego słowa, które
szawiera pod indeksemstart, jeślicanSplit(start + its length)zwracatrue, zwróćtrue. - W przeciwnym razie zwróć
false. Odpowiedzią jestcanSplit(0).
def wordBreak(s, wordDict):
def can_split(start):
# Can s[start:] be cut into dictionary words?
if start == len(s):
return True # nothing left to cut
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
return True
return False
return can_split(0)Rekurencja z memoizacją
Intuicja
Odpowiedź dotycząca reszty zależy tylko od start, który przyjmuje n + 1 wartości. W przykładzie z literą a do indeksu 20 dochodzi się po dwóch blokach po dziesięć, po dwudziestu pojedynczych literach a i na niezliczone inne sposoby, a za każdym razem wynikiem jest false. Zapisz odpowiedź dla każdego start raz i używaj jej ponownie.
Memoizacja musi zachować odpowiedzi false. Wynik true natychmiast kończy całe wyszukiwanie, więc cała powtarzana praca odbywa się w gałęziach, które kończą się niepowodzeniem.
Każdy punkt startowy sprawdza każde słowo, porównując do L liter: czas O(n × m × L), najwyżej 6 × 10^6 sprawdzeń liter i O(n) miejsca.
Algorytm
- Utwórz tablicę zapamiętującą wyniki, z jednym miejscem na każdy indeks, oznaczonym jako jeszcze nieobliczony.
- W
canSplit(start)zwróćtruena końcusalbo zapisaną odpowiedź, jeśli miejsce zawiera już wynik. - W przeciwnym razie wypróbuj każde słowo, tak jak w zwykłej rekurencji, zapisz wynik w tym miejscu, także
false, i zwróć go.
def wordBreak(s, wordDict):
memo = [None] * len(s) # memo[start]: answer for s[start:], None until worked out
def can_split(start):
if start == len(s):
return True
if memo[start] is not None:
return memo[start]
result = False
for word in wordDict:
if s.startswith(word, start) and can_split(start + len(word)):
result = True
break
memo[start] = result
return result
return can_split(0)Od dołu do góry po prefiksach z użyciem zbioru haszującego
Intuicja
Pracuj na prefiksach. Niech canEnd[i] określa, czy pierwsze i liter można podzielić; canEnd[0] ma wartość true, ponieważ pusty prefiks nie wymaga żadnych słów. Pierwsze end liter można podzielić dokładnie wtedy, gdy ich ostatni fragment, od start do end, jest słowem, a canEnd[start] ma wartość true. Wypełniając tablicę od lewej do prawej, każda potrzebna wartość canEnd[start] jest już znana.
Umieść słowa w zbiorze haszującym. Żadne słowo nie jest dłuższe niż L, więc dopasować może się tylko L fragmentów kończących się na end, niezależnie od wielkości słownika. Dla sunflowerseed wartość canEnd jest prawdziwa dla 0, 3, 7, 9 i 13; ślepy zaułek przy 7 nie szkodzi.
Dla każdej z n pozycji sprawdzanych jest najwyżej L fragmentów, a zbudowanie i zahaszowanie każdego z nich wymaga do L kroków: O(n × L²), najwyżej 1.2 × 10^5 kroków, plus O(m × L) dla zbioru.
Algorytm
- Umieść słowa w zbiorze haszującym; zanotuj największą długość
L. - Utwórz
canEndzn + 1elementami, ustawionymi nafalse, i ustawcanEnd[0]natrue. - Dla każdego
endod 1 doni każdej wartościlengthod 1 domin(L, end): jeślicanEnd[end-length]ma wartośćtrue, a fragment o tej długości kończący się naendznajduje się w zbiorze, ustawcanEnd[end]natruei przerwij. - Zwróć
canEnd[n].
def wordBreak(s, wordDict):
words = set(wordDict)
longest = max(len(word) for word in wordDict)
n = len(s)
# can_end[i]: the first i letters split into dictionary words
can_end = [False] * (n + 1)
can_end[0] = True # the empty prefix needs no words
for end in range(1, n + 1):
# The last word is s[end-length:end], and no word is longer than longest.
for length in range(1, min(longest, end) + 1):
if can_end[end - length] and s[end - length:end] in words:
can_end[end] = True
break
return can_end[n]
Pułapki i przypadki brzegowe
- Chciwe dopasowywanie. Dopasowanie najdłuższego fragmentu najpierw dzieli
carpetalnacarpeti pozostawiaal, chociaż działacar+petal; dopasowanie najkrótszego fragmentu najpierw zatrzymuje się nasunflowerseed. - Zapisywanie w pamięci podręcznej tylko odpowiedzi
true. Powtarzające się obliczenia występują w gałęziachfalse, więc przykład z samymi literami a nadal wymaga wykładniczej liczby operacji. - Utworzenie tablicy o jeden element za krótkiej.
canEndpotrzebujen + 1elementów dla długości prefiksów od 0 don. - Porównywanie poza końcem
s, na przykład słowaabcz pozostałym fragmentemab. Najpierw sprawdź długości. - W Lua i R pozycje w ciągu znaków zaczynają się od 1: fragment o długości
k, kończący się na literzee, zaczyna się nae-k+1.
Najczęstsze pytania3
Jaka jest złożoność czasowa problemu Word Break?
Tablica tworzona od dołu z użyciem zbioru haszującego działa w czasie O(m × L + n × L²), gdzie n to długość s, m to liczba słów, a L to długość najdłuższego słowa. Porównywanie każdego słowa na każdej pozycji wymaga O(n × m × L). Zwykła rekurencja ma złożoność wykładniczą.
Czy Word Break to problem programowania dynamicznego czy problem grafowy?
Oba podejścia. W programowaniu dynamicznym canEnd[i] informuje, czy pierwsze i liter można podzielić. W ujęciu grafowym każdy indeks jest węzłem, a krawędź prowadzi od i do j, gdy litery między nimi tworzą słowo; sprawdzasz wtedy, czy można dotrzeć z 0 do n. Wyszukiwanie wszerz wykonuje tę samą pracę co tabela.
Jak wyświetlić każde zdanie zamiast zwracać true lub false?
Wracanie: przy każdym indeksie wypróbuj każde pasujące słowo, rekurencyjnie przetwarzaj resztę i zapamiętuj listę zdań dla każdego indeksu. Najpierw utwórz tabelę wartości true lub false, aby ciąg znaków, którego nie da się podzielić, pomijał wyszukiwanie. Liczba zdań może rosnąć wykładniczo, więc rozmiar wyniku wyznacza czas działania.
Podobne zadania
Zadania oparte na tych samych pomysłach. Rozwiązanie dwóch lub trzech utrwala schemat.
def wordBreak(s, wordDict):
# Wpisz tutaj kodTest #1
Test #2
Test #3
Argumenty
s = "sunflowerseed" wordDict = ["sun", "flow", "flower", "seed"]
Oczekiwany wynik
true