For this challenge you need to make a given word by concatenating "pieces" (a.k.a contiguous substrings) from other words. Given a word and a list of words as input, output the fewest number of pieces needed to create the first word.
Rules
- Words consist of characters in the ASCII range 33 to 126.
- The word list may have repeats.
- Construction of words is case sensitive (you can not use the piece "Head" as part of the word "forehead".)
- Once you have used a piece in a construction, you can not use any part of that piece again (e.g if I use "lo" from "lone" as part of constructing "lolo", I cannot use "lo" from that "lone" again. However, if I had two "lone" in my word list, I could use one "lo" from each.)
- Once you use a piece, you can still make pieces out of unused substrings in the word. (E.g. If I used "tt" in "butter", I still have "bu" and "er" left over to use. However, I can't combine them into one "buer" piece.)
- If it is impossible to construct the input word using the word list given, output nothing, or something other than a positive integer.
Examples
(you only need to output the number)
"snack" ["food","Shoe","snack"]=> 1 (snack)"Snack" ["food","Shoe","snack"]=> 2 (S+nack)"frog" ["cat","dog","log"]=> 0"~~Frank~~" ["Frog~","~~Love","Hank~"]=> 4 (~~+Fr+ank~+~)"loop-de-loop" ["loop", "frien-d","-elk","pool"]=> 7 (loop+-d+e+-+l+oo+p)"banana" ["can","can","boa"]=> 4 (b+an+an+a)"banana" ["can","boa"]=> 0"13frnd" ["fr13nd"]=> 3 (13+fr+nd)
Let me know if you think of more useful test cases.
