Blind 75 · #57 · 1-D Dynamic Programming

Word Break

Medium1-D dynamic programmingTime O(n · L)Space O(n)

Word Break is a medium 1-D Dynamic Programming problem from the Blind 75. The key pattern is 1-d dynamic programming, and a good solution runs in O(n · L) time.

Problem

Determine whether text can be segmented completely into reusable dictionary words.

Examples

Example 1

Input

{"text":"applepenapple","words":["apple","pen"]}

Output

true

Example 2

Input

{"text":"duelcoder","words":["duel","coder","code"]}

Output

true

Example 3

Input

{"text":"aaab","words":["a","aa"]}

Output

false

Approach

Position i is reachable if some earlier reachable position j has a dictionary word between j and i. The whole string breaks if its end is reachable.

Pattern	1-D dynamic programming
Time	O(n · L)
Space	O(n)

Watch out for

Limit j to the longest dictionary word to avoid useless checks.

Word Break

Problem

Examples

Example 1

Example 2

Example 3

Approach

Watch out for

More 1-D Dynamic Programming problems