Frankenstein Words

Question

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.

• Mr. Xcoder: pieces are usually called contiguous substrings.

Answer 1

JavaScript, (削除) 209 (削除ここまで) 206 bytes

f=(a,b,F)=>a?[...a].map((_,i)=>[...Array(i+1)].map((_,j)=>F||b.forEach((q,k)=>!F&&~(I=q.indexOf(a[S='substring'](j,r=a.length-i+j)))&&(F=b[k]=q[S](0,I)+' '+q[S](I+r+j),a=a[S](0,j)+a[S](r)))))&&F&&1+f(a,b):0

Try it online

Returns NaN if the combination is not found.