dictionary and a string phrase. A piece is any non-empty string that is a beginning (prefix) of at least one word in dictionary; a whole word counts too.
Glue phrase together from pieces, using as few as possible (the same piece may be reused any number of times). Return the smallest number of pieces, or -1 if phrase cannot be built.
The strings here are long, so trying every piece at every position will be too slow.dictionary=['sunrise', 'setting', 'tide'], phrase='sunset' → 2
"sun" starts "sunrise" and "set" starts "setting". Two pieces are enough, and no single piece equals "sunset".
dictionary=['abab', 'b'], phrase='ababbaba' → 3
For instance "abab" + "b" + "aba", where the last piece is the start of "abab". Fewer than three pieces will not do.
dictionary=['moon'], phrase='noon' → -1
No word starts with the letter "n".
len(dictionary) ≤ 100len(dictionary[i]) ≤ 5·10⁴dictionary is at most 10⁵len(phrase) ≤ 5·10⁴dictionary=['sunrise', 'setting', 'tide'], phrase='sunset'
2
Run checks the first 3 tests in your browser. Submit checks all 172 tests on the server, hidden ones included.