PROBLEM LINK:
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[i] to stand for the minimum number of words needed to cover S[1…i]. Then we can get the recursion:
f[0] = 0;
f[i] = 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.