Can this be spelled out?
Track which positions in target are reachable, using the trie to jump ahead by whole words at a time. About 13 minutes.
A table of reachable positions
Make a table with one yes/no answer for each position in the target: "can the first i letters be fully spelled using words from the list?". Position 0 is always yes, since spelling zero letters needs no words.
The answer to the whole problem is the entry at the end, which says whether the whole target can be spelled. It is like crossing a river on stepping stones, asking which stones you can reach.
Position 0 is reachable: spelling nothing needs no words. Under each letter is whether the prefix ending there can be spelled.
Filling the table with the trie
For every reachable position, walk the trie along the target starting from that letter. Each end marker you cross, at some later position, means that later position is reachable too: a word ends exactly there, and you reached it from a place you already knew.
One trie walk per start finds every word beginning there in a single pass.
ok = [False] * (len(target) + 1) ok[0] = True # the empty start
words = ["a", "aa"], target = "aaa". Can it be spelled?
- AYes
- BNo
Show the answer
Yes. "a" + "a" + "a", or "aa" + "a": either way, dp[3] ends up true.
Can this be spelled out?
words is a list of lowercase words (a word may be used more than once), and target is a lowercase string. Return true if target can be split into a sequence of one or more words from words, one after another with nothing left over, or false otherwise.
words = ["code", "factory"], target = "codecodefactory" → true
1 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length ≤ 30 · 1 ≤ target.length ≤ 1,000 · every word and target are lowercase a-z