A search box receives text with the spaces missing. Given a dictionary and the text, split the text into dictionary words (a word may be reused) using as few words as possible. Print that number, or -1 if the text cannot be split.
Constraints
- 1 ≤ d ≤ 1000
- 1 ≤ word length ≤ 20
- 1 ≤ text length ≤ 10000
Input and output
- Input
- Line 1: d, the number of words. Line 2: d lowercase words. Line 3: the text.
- Output
- One integer.
Examples
Input 1
4
ice cream icecream s
icecreamsOutput
2"icecream" + "s" uses 2 words, fewer than "ice" + "cream" + "s".
Input 2
2
cat dog
catdoOutput
-1"do" is not a word, so the string cannot be split: -1.
Show hints
- Let best[i] be the fewest words that make up the first i characters.
- Only words up to the longest dictionary length need checking at each position.
Show the explanation
Let best[0] = 0 and best[i] be the fewest words covering text[0:i]. For each end position i, try every length L up to the longest word: if text[i−L:i] is in the dictionary (a hash set) and best[i−L] is reachable, then best[i] = min(best[i], best[i−L] + 1). The answer is best[len], or −1 if it was never reached. This is the "word break" DP with a minimum instead of a yes/no.
Original UniCircle question. Last reviewed 22 Oct 2026.