Word Break

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

Entrambi. Nella programmazione dinamica, canEnd[i] indica se le prime i lettere possono essere suddivise. In un grafo, ogni indice è un nodo, con un arco da i a j quando le lettere tra i due formano una parola, e ci si chiede se n è raggiungibile da 0. Una ricerca in ampiezza svolge lo stesso lavoro della tabella.

MedioProgrammazione dinamica Hashing

+10

Ricevi una stringa s e un elenco di parole wordDict. Restituisci true se puoi suddividere s in parti che siano tutte parole contenute 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, ciascuna 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 minuscole inglesi.
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 lascia er, con cui non inizia nessuna parola, quindi la prima parola che corrisponde 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: Sia pine + apple sia pineapple lasciano tart. Lì si adatta solo tar, che lascia una t isolata, quindi nessun taglio funziona.

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 cambia il tempo di esecuzione?

Suggerimenti

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

0 di 3 aperti

Soluzione

Impegnarsi su una parola alla volta non funziona, e provare ogni possibile taglio ha una complessità esponenziale. Ma la possibilità di suddividere il resto di s dipende solo dal punto in cui inizia, quindi ci sono solo n + 1 domande. Di seguito, 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

Il primo pezzo deve essere una parola che inizi con s. Prova ogni parola del genere e poni la stessa domanda sulle lettere rimanenti; un resto vuoto significa che ogni lettera è stata suddivisa. Provando ogni prima parola e poi ogni seconda parola, non puoi perderti nessuna suddivisione valida.

Controlla più e più volte gli stessi resti. Con 299 copie di a seguite da una b e le parole a, aa fino a dieci a, più di 10^89 modi di suddividere le a in blocchi arrivano alla b e falliscono, e la ricorsione li prova tutti.

Algoritmo

Scrivi canSplit(start): le lettere da start fino alla fine possono essere suddivise? Se start è uguale alla lunghezza di s, restituisci true.
Per ogni parola contenuta in s all'indice start, se canSplit(start + its length) è true, restituisci true.
Altrimenti 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 memorizzazione

Intuizione

La risposta per un resto dipende solo da start, che assume n + 1 valori. Nell'esempio con le a, si raggiunge il resto all'indice 20 dopo due blocchi da dieci, dopo venti a singole e in innumerevoli altri modi, e ogni volta il risultato è false. Memorizza una volta la risposta per ogni start e riutilizzala.

La memoizzazione deve conservare le risposte false. Un true termina subito l'intera ricerca, quindi tutto il lavoro ripetuto si trova nei rami che falliscono.

Ogni start prova tutte le parole, confrontando fino a L lettere: tempo O(n × m × L), al massimo 6 × 10^6 controlli di lettere e spazio O(n).

Algoritmo

Crea una memoizzazione con uno slot per ogni indice, ciascuno contrassegnato come non ancora calcolato.
In canSplit(start), restituisci true alla fine di s, oppure la risposta memorizzata se lo slot contiene un valore.
Altrimenti prova ogni parola come nella ricorsione semplice, memorizza il risultato nello slot, incluso false, e restituiscilo.

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

Lavora sui prefissi. Sia canEnd[i] a indicare se le prime i lettere possono essere suddivise; canEnd[0] è true, perché il prefisso vuoto non richiede parole. Le prime end lettere possono essere suddivise esattamente quando l’ultimo segmento, da start a end, è una parola e canEnd[start] è true. Riempito da sinistra a destra, ogni canEnd[start] necessario è già noto.

Inserisci le parole in un insieme hash. Nessuna parola è più lunga di L, quindi solo i L segmenti che terminano in end possono corrispondere, a prescindere dalla dimensione del dizionario. Per sunflowerseed, canEnd è true in corrispondenza di 0, 3, 7, 9 e 13; il vicolo cieco in 7 non crea problemi.

Ognuna delle n posizioni cerca al massimo L segmenti, ciascuno dei quali richiede fino a L passaggi per essere creato e sottoposto a hashing: O(n × L²), al massimo 1.2 × 10^5 passaggi, più O(m × L) per l’insieme.

Algoritmo

Inserisci le parole in un insieme hash; annota la lunghezza massima L.
Crea canEnd con n + 1 elementi, tutti false, e imposta canEnd[0] su true.
Per ogni end da 1 a n e ogni length da 1 a min(L, end): se canEnd[end-length] è true e la parte di quella lunghezza che termina in end è nell'insieme, imposta canEnd[end] su true e fermati.
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

Suddividere in modo greedy. Scegliere prima la parola più lunga suddivide carpetal in carpet e lascia isolato al, anche se car + petal funziona; scegliere prima la parola più corta si blocca su sunflowerseed.
Memorizzare solo le risposte true. Il lavoro ripetuto si trova nei rami false, quindi l’esempio con le a rimane esponenziale.
Creare una tabella con una voce in meno. canEnd richiede n + 1 voci, per lunghezze del prefisso da 0 a n.
Confrontare oltre la fine di s, ad esempio la parola abc con il resto ab. Controlla prima le lunghezze.
In Lua e R, le posizioni delle stringhe iniziano da 1: una parte di lunghezza k che termina alla lettera e inizia a e-k+1.

Domande frequenti3

Qual è la complessità temporale di Word Break?

La tabella bottom-up con un insieme hash ha una complessità di O(m × L + n × L²), dove n è la lunghezza di s, m il numero di parole e L la parola più lunga. Confrontare ogni parola in ogni posizione ha un costo di O(n × m × L). La ricorsione semplice ha una complessità esponenziale.

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

Entrambi. Nella programmazione dinamica, canEnd[i] indica se le prime i lettere possono essere suddivise. In un grafo, ogni indice è un nodo, con un arco da i a j quando le lettere tra i due formano una parola, e ci si chiede se n è raggiungibile da 0. Una ricerca in ampiezza svolge lo stesso lavoro della tabella.

Come fai a elencare ogni frase invece di restituire vero o falso?

Backtracking: a ogni indice prova ogni parola che ci sta, richiama ricorsivamente sul resto e ricorda l’elenco delle frasi per ogni indice. Esegui prima la tabella dei valori true o false, così una stringa che non può essere suddivisa salta la ricerca. Il numero di frasi può crescere in modo esponenziale, quindi la dimensione dell’output determina il tempo di esecuzione.

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

Test #1

Test #2

Test #3

Argomenti

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

Output atteso

true

Word Break

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Prova ogni parola in ogni posizione

Ricorsione con memorizzazione

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

Trappole e casi limite

Domande frequenti3

Problemi simili