Given a string of letters and a set of words, output an ordering of the words so that they can be found in the string by dropping letters that are not needed. Words may occur more than once in the word set. The input string and all words will consist of 1 to 1000 lower case letters each. The letters to be dropped may occur inside words or between words.
Your program or function can accept the letter string and words as lists, a string, or from STDIN, and must output all words in a correct order as a list or string output. If there is more than one correct solution, only output one of them. If there is no possible correct solution, output an empty list or an empty string.
Examples:
dogcatfrog cat frog dog
-> dog cat frog
xxcatfixsxhingonxgrapexxxfishingcxat cat grape catfish fishing
-> catfish grape fishing cat
dababbabadbaccbcbaaacdacdbdd aa bb cc dd ba ba ba ab ac da db dc
-> da ab ba ba ba cc bb aa ac dc db dd
flea antelope
->
(no solution)
This is code golf. Lowest number of bytes wins.
Edit: Explained that extra characters can be inside words.
cc
beforebb
but thebb
andcc
substrings only appear once and thebb
substring appears first. \$\endgroup\$ccbcb
part of the string we output thecc
then outputbb
after dropping the middlec
. \$\endgroup\$