Letter Coverage

Problem Description

The letter/word coverage problem is the problem of finding the minimum number of words from the five-letter-words set (see Five Letter Words) to cover X letters of the alphabet.

The problem has a couple of variations: we might provide a set of letters, and search for the smallest number of words that can cover those particular letters. Or we might give an integer N <= 26, and search for the smallest number of words that can cover the first N letters of the alphabet.

We may also wish to restrict our search to the first M words of the 5757 total five letter words.

For the sake of simplicity, we will start with the problem of considering the first N letters of the alphabet, and the shortest sequence of words that will provide coverage of those first N letters of the alphabet.

Solution

A Simpler Example

Suppose we are considering 2-letter words taken from a 5-letter alphabet abcde. We can represent a given word as a binary string/bit vector:

ab = 11000
ce = 00101
ae = 10001

etc. Now, we wish to write a dynamic program that will find the smallest set of words such that taking the union of each bit vector gives 11111.

Solution Procedure

To solve dynamic programming problems, apply these three steps:

1. Formulate answer as recurrence relation/recursive algorithm

2. Show that the number of parameters taken on by the recurrence is bounded by a polynomial

3. Specify the order of evaluation for the recurrence so that partial results that are needed are always available