Sentence Reconstructions — Solution & Editorial

Back to the Problem

dp[i] = number of ways to segment the first i characters; extend by every dictionary word that ends at position i. Bounding word length (or a trie/Aho–Corasick) keeps it efficient.

Complexity: O(|text| · maxwordlen)