File WordBreak.h

↰ Parent directory (ADS/string)

Is it Italian? (exercise 13.13): a string s[ 0 .

Definition (ADS/string/WordBreak.h)

Detailed Description

. n - 1 ] with no spaces is a sequence of words of a dictionary if one of its prefixes s[ 0 .. j ) is and s[ j .. i ) is a word: DP[ i ] = true if and only if there is j < i with DP[ j ] and s[ j .. i ) in the dictionary, DP[ 0 ] = true; O( n^2 ) lookups, or O( n w ) if no word is longer than w. The words are read back from the table.

The contracts [see File Contract.h]: the words found, joined, give back the string. The operations are defined in WordBreak.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, exercise 13.13, https://algoritmicamente.it/materiali/libro/capitoli/cap13.pdf

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions