One-dimensional Dynamic Programming
A table of yes and no
Not every table holds a number. Reachability over prefixes is often all you need.
Key idea
The state sentence, again
The answer at position i is whether the first i characters can be fully consumed by valid pieces. Base case: the empty prefix is reachable.
The transition asks, for each position j before i, whether j was reachable and whether the piece from j to i is valid. If any such j exists, i is reachable.
This is the counting lesson with any in place of a sum. The structure is identical and the reading of the table is different.
Tip
One witness is enough
The inner loop stops at the first j that works, because reachability is a yes-or-no question and one route is as good as any other. The counting version cannot break, since it needs every contributing term.
That difference is worth noticing whenever you convert between counting and reachability versions of a problem: the break is valid in one and a bug in the other.
Edge cases
The empty input is reachable
An empty string is trivially splittable, and the base case says so. Some problem statements disagree and want False; read carefully rather than assuming.
This is the same base-case-of-one question from the counting lesson wearing different clothes. In both cases the identity element of the operation is the right base value, and here that is True for an and-chain.
Cost
Cost, and the trie improvement
The double loop is O(n squared) positions, and each check slices the string and hashes it, which costs the piece length. So the honest figure is O(n squared times L) or O(n cubed) when pieces can be as long as the string.
Storing the pieces in a trie removes the slicing: walk forward from j through the trie one character at a time, and every prefix match is discovered along the way with no substring built. That is a genuine improvement and a good thing to raise, and it is where Unit 11 pays off again.
Key idea
Only checking lengths that exist
A cheaper improvement needs no new structure: only try lengths that some piece actually has. If the longest piece is 10 characters, the inner loop never needs to look back further than 10.
That turns the inner loop from O(n) into O(longest piece), which on realistic inputs is a large saving for one line of setup.
Predict the output: one witness is enough
Positions reachable by exact pieces are computed, and for each one every cut point that reaches it is listed. Type the four lines it prints.
Word Break
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.