#3291
Minimum Number of Valid Strings to Form Target I
medium · 21.7% accepted · 176 likes · top 2%
array · string · binary search · dynamic programming · trie · segment tree · rolling hash · string matching · hash function
Description
You are given an array of strings words and a string target.
A string x is called valid if x is a prefix of any string in words.
Return the minimum number of valid strings that can be concatenated to form target. If it is not possible to form target, return -1.
Solution