You are given a list of strings and you have to find out which strings can be made of concatenating other strings present in the list. Solve the problem by checking every string if it entirely consists of other strings present in the list.

This can be solved by dynamic programming. Maintain a boolean dp array, where dp[i] is true when, substring from index 0 to i of that string is made of concatenation of other strings from the list. So we also can say dp[j] is true if substring from i+1 to j is present in the list. So,

dp[j] = dp[i] | (substring from i+1 to j is present)

If string length is k then it can be solved in k2 time complexity.

Total Time Complexity: O(n × k2)

Statistics

46% Solution Ratio
code_hard123Earliest, Mar '20
nusuBotFastest, 0.0s
mahdi.hasnatLightest, 131 kB
probableShortest, 601B
Toph uses cookies. By continuing you agree to our Cookie Policy.