Combinatorics or another approach? [closed]

Question

I've recently read this problem, first, I thought of a combinatorial approach, but it seems nobody - along the contestants - has submitted such a solution. Is a solution using combinatorics possible? If not, what's the solution? The problem briefly is: Given a dictionary of M words, where any two words can be joined together and possibly overlapping some letters with each other, find how many strings of length N can be formed from the dictionary. The combinatorial approach has a downer limit of M!, then for each two consecutive words, you should try intersecting them. That's what I thought of. I doubt it'd work. Please help?

Answer 1

Don't confuse combinatorics with brute force. This is clearly a combinatorial counting problem but the time limit also rules out any brute force solution.

I think you can solve this with dinamic programming. For example, suppose our substring are "CAT and TCAT" and we need to cover a word of size 100

if we start with "CAT" we have 97 letters left if we start with "TCAT" we have 96 letters left.

So, if f(n) is the number of solutions for a matching of size n, we would have f(100) = f(97) + f(96).

Note, however, that this is clearly too simplified and not enough - you also need to cover the cases where the strings overlap and make sure that you don't count the same solution twice.