Some queries on strings

Правка en3, от 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.

Thanks.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский OneClickAC 2019-09-02 19:51:07 53
en2 Английский OneClickAC 2019-09-02 14:36:18 28
en1 Английский OneClickAC 2019-09-02 14:34:57 913 Initial revision (published)