You are not logged in. Please login at to post your questions!


KGP13G - Editorial



Editorialist: Jingbo Shang


Easy - Medium


Dynamic Programming, Trie


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].


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.

This question is marked "community wiki".

asked 29 Dec '13, 11:27

admin's gravatar image

0★admin ♦♦
accept rate: 36%

wikified 29 Dec '13, 11:28

kunal361's gravatar image


can anyone explain this with an example?

(20 Mar '14, 09:28) milindshah0771★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 29 Dec '13, 11:27

question was seen: 1,657 times

last updated: 20 Mar '14, 09:28