Some queries on strings

Revision en3, by OneClickAC, 2019-09-02 19:51:07

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.



  Rev. Lang. By When Δ Comment
en3 English OneClickAC 2019-09-02 19:51:07 53
en2 English OneClickAC 2019-09-02 14:36:18 28
en1 English OneClickAC 2019-09-02 14:34:57 913 Initial revision (published)