Per esempio il mio input è questo dizionario s = ["mezzogiorno", "n", "o", "noo", "Buono", "Buongiorno", "sposare", "io", "marryme", "aria", "r", "airbag" ]. L'output dovrebbe essere un elenco di parole composte. come Good noon, airbag.
Per esempio il mio input è questo dizionario s = ["mezzogiorno", "n", "o", "noo", "Buono", "Buongiorno", "sposare", "io", "marryme", "aria", "r", "airbag" ]. L'output dovrebbe essere un elenco di parole composte. come Good noon, airbag.
Un approccio è generare i composti dal dizionario:
Controllare l'inclusione della concatenazione del prodotto cartesiano del dizionario con se stesso. Questo scopre che ("Buono", "mezzogiorno") si verifica quando "Buongiorno" appare nel dizionario.
Questo può essere reso più veloce con un prefisso trie (indice del prefisso della stringa) sul dizionario ed evitando il metodo diretto di prendere il prodotto cartesiano e non concatenarlo. Non descriverò l'implementazione. Nel caso in cui sia permesso iniziare con un prefisso sconosciuto e terminare con una parola conosciuta, dovrebbe essere usato anche un suffisso trie.
Si può anche avvicinarsi a questo come spezzare le parole composte:
Significa che "Goodnoon" dato un dizionario di parole trova le parole che compongono il composto. In questo caso: [('Buono', 'mezzogiorno')]. L'output di questo può essere ridotto al problema precedente riducendo l'insieme di partizioni a non-vuoto.
Per risolvere questo si trova per tutte le parole che sono un prefisso di questa parola e quindi tutte le parole che sono prefissi del composto con la parola precedente rimossa, questo viene ripetuto fino a quando non ci sono parole corrispondenti o il composto viene ridotto al stringa vuota. Ad ogni passaggio, questo è un problema di intersezione tra prefisso e indice di suffisso.
Una parola composta inizia con un'altra parola. Quindi il primo passo sarebbe quello di ordinare le parole per lunghezza e provare parole più brevi come prefissi di parole più lunghe.
Quelli che hanno un'altra parola come prefisso, passano al round successivo, dove provi a vedere se continuano oltre il punto del prefisso con un'altra parola più breve. È utile mantenere le parole come un elenco di parti : (prefisso, parte rimanente), quindi dividerle una volta individuato il prefisso e controllare solo la parte rimanente.
Con un po 'di attenzione, questo funziona per parole composte composte da più di 2 parti. Aspettatevi risultati divertenti con parole composte che sono parti di parole composte persistenti: ["foo", "bar", "baz", "foobar", "foobarbaz"].
Leggi altre domande sui tag algorithms