Given a list of words and q queries are given . In each query i am given a string and i have to tell which strings are combination of two or more words from the initial given words. I am solve this if each word is a combination of two mords using hashing and extend it to more words case using dp. Does there exists a better solution somewhat linear in the number of words using some advanced data structure?
eg.
a
b
c
1
abc
Output
yes
I'm not sure of a linear solution but you can surely do better than the obvious quadratic solution.Use the fact that among the input words,there would be only sqrt(sum of lengths of input words) different lengths.Using this you can bring down the complexity to (sum of lengths of query strings)*sqrt(sum of lengths of input words).
Thanks a lot :)