KGP13G - Editorial

PROBLEM LINK:

Practice
Contest

Editorialist: Jingbo Shang

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Dynamic Programming, Trie

PROBLEM:

Given K words W[1…K], determine the minimum number of words need to exact cover (without any overlaps) a given string S[1…n].

EXPLANATION:

It is worth to note that although the number corresponds many characters, each character is only mapped to one number. Therefore, we can translate the characters to numbers.

After that, we can further observe that the exact cover can be performed in order such that each time the covered part is the prefix of the string. That is, given any possible solutions, we can always arrange the order of words to make sure that the covered part is always a prefix of the string. This gives us the opportunity of dynamic programming.

Use f* to stand for the minimum number of words needed to cover S[1…i]. Then we can get the recursion:

f[0] = 0;
f* = min{ f[j] + 1 };  for all 0 <= j < i and S[j+1 .. i] is a word.

This dynamic programming is O(nKL) if we implement by trying all words. Here L is the maximum length of words. We can improve this situation by building a Trie for the word list. With Trie, the time complexity can be improved to O(nL), because we do not perform any extra matching between the string and words.

can anyone explain this with an example?

Can anyone explain what is wrong with my approach? I am basically doing the same dp-trie approach everyone else is following. Code: https://code.hackerearth.com/c60885x

Check out some examples of dynamic programming itself. Once you understand LIS, LCS, and Edit-Distance you’ll find this problem quite simple.