#3292

Minimum Number of Valid Strings to Form Target II

hard · 20.4% accepted · 85 likes · top 2%

array · string · binary search · dynamic programming · segment tree · rolling hash · string matching · hash function

⊣ practice⊣ open on leetcode ↗

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