Word Puzzle is a puzzle to generate a given sentence using pieces of given word. At this point, we assume that there are infinite numbers of pieces for each given word. For example, when given words are [“ba”, “na”, “n”, “a”], there are infinite pieces of ba, na, n, and a. At this point, if the sentence to generate is banana, it can be generated by using 4 pieces of ba, na, n, and a. Also, you can generate banana using 3 pieces of ba, na, and na. Given an array strs containing available pieces of words and sentence to generate t as parameters, write a function solution to return the minimum number of pieces to generate given sentence. If the given sentence cannot be generated, return -1.

  • strs is an array containing available pieces of words, and its length is between 1 and 100.
  • There are no duplicated elements in strs.
  • Pieces of words are in string format, and length of all pieces is between 1 and 5.
  • t is a sentence to generate, and its length is between 1 and 20,000.
  • All strings consist of lower-case alphabet only.

strs t result
["ba","na","n","a"] "banana" 3
["app","ap","p","l","e","ple","pp"] "apple" 2
["ba","an","nan","ban","n"] "banana" -1

Example #1
This is the same with an example in problem statement.

Example #2
apple can be generated by using 2 pieces of ap and ple, return 2.

Example #3
Since banana cannot be generated using given words, return -1.

Result Stop
Result of [Run Test] or [Submit] will be displayed here