Target From Word Beginnings

Medium

You get a list of words vocab and a string target. A piece is any non-empty string that is a beginning (prefix) of at least one word in vocab; a whole word counts too. Glue target together from pieces, using as few as possible (the same piece may be used many times). Return the smallest number of pieces, or -1 if target cannot be built.

Example 1

vocab=["sun", "flower"], target="sunflow" → 2

sun is a start of sun and flow is a start of flower: two pieces.

Example 2

vocab=["abc", "b"], target="abab" → 2

ab + ab: both pieces are a start of abc.

Example 3

vocab=["cat"], target="dog" → -1

No word starts with d.

Constraints

1 ≤ len(vocab) ≤ 100
1 ≤ len(vocab[i]) ≤ 5000
The total length of the words in vocab is at most 10⁵
1 ≤ len(target) ≤ 5000
All strings consist of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Trie Segment Tree Array String Binary Search Dynamic Programming String Matching Hash Function Rolling Hash

Similar problems

Phrase From Word Beginnings, Long Edition Hard Bookend Word Pairs Easy Framing Word Pairs Hard Longest Shared Run Medium Words Hidden in a Text Medium

Input

vocab=["sun", "flower"], target="sunflow"

Expected

Run checks the first 3 tests in your browser. Submit checks all 152 tests on the server, hidden ones included.