Hi folks, Got to know about this problem from a friend. It was asked in codenation's coding round/interview last year.

Any leads on a better approach than $$$O(n^2)$$$ will be appreciated.

Question — You are given n strings and q queries. Each query is also in the form of a string (say $$$q_i$$$). You have to reply with true if this string can be formed by concatenating any of the n strings given earlier.

For example — Suppose $$$n = 3$$$ and the strings are $$$abc$$$ , $$$bc$$$ and $$$cd$$$.

So $$$abcabc$$$ is a valid string because you can use $$$abc$$$ twice. (There is no constraint on the number of times you can use any given string.)

Also, $$$bccdabc$$$ is a valid string as we can use the given strings in the order $$$2$$$, $$$3$$$ and $$$1$$$.

Sum of all the strings in query is $$$\leq 10000$$$

My friend final_tsu helped me in coming with a $$$O(n^2)$$$ approach using Trie and DP.

Thanks.