Word Break

Q: Qual è la complessità temporale di Word Break?

La tabella bottom-up con un insieme hash richiede un tempo O(m × L + n × L²) , dove n è la lunghezza di s , m il numero di parole e L la parola più lunga. La creazione dell’insieme legge ogni parola una volta e, per ciascuna delle n posizioni, cerca al massimo L parti composte da un massimo di L lettere. Se invece confronti ogni parola in ogni posizione, il tempo è O(n × m × L) . La ricorsione semplice senza memoizzazione è esponenziale.

MedioProgrammazione dinamica Hashing

+10

Hai una stringa s e un elenco di parole wordDict. Restituisci true se puoi suddividere s in parti in modo che ogni parte sia una parola presente in wordDict, e false altrimenti.

Le parti mantengono il loro ordine e, insieme, usano ogni lettera di s esattamente una volta. Una parola può essere usata un numero qualsiasi di volte e non devi usare tutte le parole.

Funzione

wordBreak(s: string, wordDict: string-array) → boolean

sstring: la stringa da suddividere in parole
wordDictstring-array: le parole che puoi usare, tutte le volte che vuoi
Restituisceboolean: vero se s può essere suddivisa in parole del dizionario, falso altrimenti

Vincoli

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s e ogni parola contiene solo lettere inglesi minuscole.
Le parole in wordDict sono tutte diverse.

Esempi

Input: s = "sunflowerseed"wordDict = ["sun", "flow", "flower", "seed"]
Output: true
Spiegazione: Dividila in sun, flower, seed. Prendere flow dopo sun non porta a nulla, perché nessuna parola inizia con er, che è ciò che rimane, quindi la prima parola che va bene non è sempre quella giusta.

Input: s = "bananaban"wordDict = ["ban", "ana"]
Output: true
Spiegazione: ban + ana + ban copre la stringa e usa ban due volte, il che è consentito.

Input: s = "pineappletart"wordDict = ["pine", "apple", "pineapple", "tar"]
Output: false
Spiegazione: La stringa inizia con pine + apple oppure con pineapple, e in entrambi i casi rimane tart. L’unica parola che ci sta è tar, che lascia una t isolata, quindi nessun taglio funziona.

+21 test nascosti all’invio

Per approfondire

Restituisci il minor numero di parole che un taglio valido può usare, oppure -1 se s non può essere tagliata. Cosa cambia nella tabella e il tempo di esecuzione cambia?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Tagliare in modo greedy non funziona in nessuna delle due direzioni: prendere prima la parola più corta fa sì che sunflowerseed venga divisa in sun + flow, mentre prendere prima quella più lunga divide carpetal in carpet e lascia al isolato. Quindi devi provare le diverse possibilità, e una stringa può essere divisa in un numero esponenziale di modi. La chiave è che la possibilità di dividere il resto della stringa dipende solo dal punto in cui inizia il resto, quindi ci sono solo n + 1 domande diverse. Qui sotto, n è la lunghezza di s, m il numero di parole e L la lunghezza della parola più lunga.

Prova ogni parola in ogni posizione

Corretto, ma non termina sui test più grandi

Intuizione

Leggi s da sinistra. Qualunque sia il primo pezzo, deve essere una parola con cui inizia s. Prova ciascuna di queste parole e, per ognuna, poni la stessa domanda sulle lettere rimanenti. Se una qualsiasi parola porta a una suddivisione completa, la risposta è true. Se nessuna ci riesce, è false. Quando non rimane nulla, hai suddiviso tutte le lettere, quindi è un successo.

Questo prova ogni possibile prima parola, poi ogni possibile seconda parola e così via, quindi non può tralasciare una suddivisione valida, e ogni true restituito corrisponde a una suddivisione reale.

È lento perché controlla più volte le stesse parti rimanenti. Prendi 299 copie di a seguite da una b, con le parole a, aa e così via fino a dieci a. Ogni modo di suddividere le a in blocchi di al massimo dieci arriva alla b e fallisce lì, e ci sono più di 10^89 modi del genere. La ricorsione deve provarli tutti prima di poter rispondere false.

Algoritmo

Scrivi una funzione di supporto canSplit(start) che indica se le lettere dall’indice start fino alla fine possono essere suddivise in parole.
Se start è uguale alla lunghezza di s, restituisci true.
Per ogni parola, verifica se s la contiene a partire dall’indice start.
Se la contiene e canSplit(start + length of the word) è true, restituisci true.
Se nessuna parola funziona, restituisci false. La risposta è canSplit(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)

Ricorsione con memoizzazione

Intuizione

La risposta per un resto dipende solo dal punto in cui inizia, e start assume solo n + 1 valori. Nell'esempio con le a, si raggiunge il resto che inizia all'indice 20 dopo due blocchi di dieci, dopo venti a singole e in un enorme numero di altri modi, e la risposta è false ogni volta. Memorizza la risposta per ogni punto di partenza la prima volta che la calcoli, quindi recuperala in seguito.

Uno slot della memoizzazione ha bisogno di tre stati: non ancora calcolato, true e false. Le risposte false sono quelle che contano. Un true termina subito l'intera ricerca, quindi il lavoro ripetuto dalla ricorsione semplice si trova tutto nei rami che falliscono.

Ogni punto di partenza viene calcolato una volta e prova ogni parola, confrontando fino a L lettere, quindi il tempo è O(n × m × L): al massimo 300 × 1000 × 20 = 6 × 10^6 controlli di lettere in questo caso. La memoizzazione e lo stack delle chiamate richiedono O(n) spazio e le chiamate si annidano fino a una profondità di 300.

Algoritmo

Crea una tabella con uno slot per ogni indice, ciascuno contrassegnato come non ancora calcolato.
In canSplit(start), restituisci true alla fine della stringa e restituisci la risposta memorizzata se lo slot per start ne contiene una.
Altrimenti prova ogni parola che inizia in start, come nella ricorsione semplice, e fermati alla prima il cui resto può essere suddiviso.
Memorizza il risultato nello slot, incluso false, e restituiscilo.
Restituisci canSplit(0).

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)

Dal basso verso l'alto sui prefissi con un insieme hash

Intuizione

Inverti il ragionamento e lavora sui prefissi. Sia canEnd[i] a indicare se le prime i lettere possono essere suddivise in parole. Il prefisso vuoto non richiede parole, quindi canEnd[0] è true. Le prime end lettere possono essere suddivise esattamente quando l’ultima parte, le lettere da start a end, è una parola e le lettere che la precedono possono essere suddivise, cioè canEnd[start] è true. Riempi la tabella da sinistra a destra e ogni canEnd[start] di cui hai bisogno è già noto.

Invece di confrontare tutte le m parole a ogni posizione, inserisci le parole in un insieme hash e cerca le possibili parti finali. Nessuna parola è più lunga di L, quindi solo le L parti che terminano in end possono corrispondere. Con sunflowerseed, canEnd diventa true a 0, a 3 (sun), a 7 (flow), a 9 (flower) e a 13 (seed dopo la posizione 9), quindi la risposta è true. La posizione 7 non porta da nessuna parte, perché nessuna parola inizia con er, e alla tabella non importa.

Ci sono n posizioni, ognuna cerca al massimo L parti, e costruire e calcolare l’hash di una parte richiede fino a L passaggi. Si tratta di O(n × L²), al massimo 300 × 20 × 20 = 1.2 × 10^5 passaggi sulle lettere, a prescindere da quanto sia grande il dizionario. La costruzione dell’insieme legge ogni parola una volta, O(m × L), quindi il totale è O(m × L + n × L²). L’insieme contiene le parole, O(m × L) lettere, e la tabella contiene n + 1 flag. Non c’è ricorsione.

Algoritmo

Inserisci ogni parola in un insieme hash e annota la lunghezza L della parola più lunga.
Crea canEnd con n + 1 elementi, tutti false, e imposta canEnd[0] su true.
Per ogni end da 1 a n, prova ogni length da 1 a min(L, end).
Se canEnd[end-length] è true e il pezzo di quella lunghezza che termina in end è nell'insieme, imposta canEnd[end] su true e interrompi i tentativi con le lunghezze.
Restituisci 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]

Trappole e casi limite

La maggior parte delle risposte sbagliate deriva dal decidere troppo presto di fare un unico taglio o da una ricerca che non tiene mai conto dei propri insuccessi.

Tagliare in modo greedy. Prendere prima la parola più lunga divide carpetal in carpet e lascia al, anche se car + petal funziona. Prendere prima la parola più corta non funziona con sunflowerseed.
Controllare solo che ogni lettera di s compaia in una parola. Con le parole aaaa e aa, ogni pezzo ha una lunghezza pari, quindi aaaaaaa, sette lettere, non può essere suddivisa.
Memorizzare nella memo solo le risposte true. Una risposta true termina comunque la ricerca. Il lavoro ripetuto si trova nei rami false, quindi una memo senza di essi continua ad avere una complessità esponenziale.
Creare una tabella con una voce in meno. canEnd[i] riguarda le prime i lettere, e sia 0 sia n sono valori validi, quindi servono n + 1 voci.
Confrontare oltre la fine di s quando una parola è più lunga della parte rimanente, ad esempio la parola abc rispetto a ab. Controlla le lunghezze prima di confrontare le lettere.
In Lua e R, le posizioni delle stringhe iniziano da 1: un pezzo di lunghezza k che termina alla lettera e inizia alla lettera e-k+1.

Domande frequenti4

Qual è la complessità temporale di Word Break?

La tabella bottom-up con un insieme hash richiede un tempo O(m × L + n × L²), dove n è la lunghezza di s, m il numero di parole e L la parola più lunga. La creazione dell’insieme legge ogni parola una volta e, per ciascuna delle n posizioni, cerca al massimo L parti composte da un massimo di L lettere. Se invece confronti ogni parola in ogni posizione, il tempo è O(n × m × L). La ricorsione semplice senza memoizzazione è esponenziale.

Perché un approccio greedy non funziona per Word Break?

Una regola greedy sceglie una parola e non ci ripensa mai. La scelta della parola più lunga per prima divide carpetal in carpet e al, mentre car + petal funziona. La scelta della parola più corta per prima divide sunflowerseed in sun + flow e si blocca su erseed. La programmazione dinamica tiene traccia di ogni posizione raggiungibile con qualche suddivisione, così non perde mai quella giusta.

Word Break è un problema di programmazione dinamica o un problema di grafi?

Entrambe le rappresentazioni funzionano. Come programmazione dinamica, canEnd[i] risponde alla domanda se le prime i lettere possono essere suddivise, partendo da prefissi più brevi. Come grafo, ogni indice è un nodo con un arco da i a j quando le lettere da i a j formano una parola, e ci si chiede se il nodo n è raggiungibile dal nodo 0. Una ricerca in ampiezza con un insieme di nodi visitati svolge lo stesso compito della tabella.

Come fai a elencare ogni frase invece di restituire true o false?

Usa il backtracking: a ogni indice prova ogni parola compatibile e richiama ricorsivamente la funzione sul resto, costruendo la frase man mano. Ricorda l’elenco delle frasi per ogni indice, così ogni parte restante viene risolta una sola volta. Esegui prima la tabella dei valori vero o falso, in modo che una stringa che non può essere suddivisa salti la ricerca. Il numero di frasi può crescere in modo esponenziale, quindi la dimensione dell’output determina il tempo di esecuzione.

Python

def wordBreak(s, wordDict):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "sunflowerseed"
wordDict = ["sun", "flow", "flower", "seed"]

Atteso

true

Word Break

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni parola in ogni posizione

Ricorsione con memoizzazione

Dal basso verso l'alto sui prefissi con un insieme hash

Trappole e casi limite

Domande frequenti4

Problemi simili