×

# KGP13G - Editorial

Editorialist: Jingbo Shang

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.

This question is marked "community wiki".

19.8k350498541
accept rate: 36%

4★kunal361
6.0k133272

can anyone explain this with an example?

(20 Mar '14, 09:28)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,852
×2,212
×1,722
×186
×14

question asked: 29 Dec '13, 11:27

question was seen: 1,657 times

last updated: 20 Mar '14, 09:28