Word Game
Time limit2sMemory limit128 MB
Given a string and a dictionary of words, find the minimum number of characters to delete from the string so the rest is a concatenation of dictionary words in order.
- Level
Medium6 of 10
- Topics
- Dynamic programming, String matching, Greedy, String
- Solved
- No attempts yet
Problem
You are given a dictionary containing w words. Every dictionary word consists only of lowercase English letters from a to z, and each word has length at most 25.
You are also given a string S of length l. By removing some characters from S, the remaining characters can be written as a concatenation of words from the dictionary. Characters that are not removed must keep their original order.
Compute the minimum number of characters that must be removed from S so that the remaining string can be represented by dictionary words.
Input
The first line contains w and l (1 <= w <= 600, 2 <= l <= 300).
The second line contains the string S.
Each of the next w lines contains one dictionary word.
Output
Print the minimum number of characters that must be removed from S.
Hint
For browndcodw, removing the two d characters leaves browncow, which can be represented as the two dictionary words brown and cow.