Try to find a word in the dictionary that has most letters given

algorithmsdictionarystrings

I recently came across an algorithm design problem that I'd like some help with:

Given some letters, for example a,e,o,g,z,k,l,j,w,n and a dictionary of words. Find a word in the dictionary that has most letters.

My first attempt:

Let us assume that the dictionary is in a tree. Start by finding the permutations of the given letters, here we could be using recursion, we can prune the recursion tree, by checking the letters in the dictionary. and we maintain a variable which holds the largest string formed till now.

How is this solution? Is there a better one?

Best Answer

The best you can do is reduce the number of comparisons to the number of letters in the dictionary.

sought: a,e,o,g,z,k,l,j,w,n

make index of alphabet where sought keys have value 1, the rest: 0.
```
   index={a:1, b:0, c:0, d:0, e:1, f:0, g:1...}
```

Iterate over each word of dictionary. Add value of the index to sum of that word. Remember word position and value if it's greater than best.

max=0;
max_index=0;

foreach(dictionary as position=>word)
{
    sum=0;
    foreach(word as letter)
    {
      sum += index[letter];
    }
    if(sum > max)
    {
        max = sum;
        max_index = position;
    }
}

max_index points to the word with maximum of the letters. Some optimizations may be skipping words shorter than the current max, or starting with dictionary sorted by word length and stopping once word length drops to max currently found.

This is assuming letters from the list are allowed to repeat any number of times. If they are not, make the index contain number of given type of letters, increment sum by 1 on each find of non-zero index value and decrement the index. (reset index on each line.)

In this time optimizations could be, on top of the previous ones: abort checking word if less than max-sum letters remain, abort operation if word with all letters is found.

Related Solutions

Algorithms – Possible Improvements to Damerau-Levenshtein Algorithm

I had to look up the Damerau-Levenshtein distance on wikipedia, so forgive me if this is wrong. But it looks like it only allows for transposing adjacent letters and not any arbitrary ones. So your example "abcdef" -> "abcfad" with transpose of d and f doesn't work. It seems to me you have modified the definition of the algorithm and are no longer calculating the Damerau-Levenshtein distance.

Longest list of words with matching start and end letters

I think this is related to the longest path (LP) problem that you mentioned, but it's a little different. The primary difference is that the LP problem has a higher degree of connectivity than what your suggested problem does. By restricting your connections to the last and first letters, you remove a large number of potential combinations.

Here's how I would recommend tackling this one:

For each word in the list, count the possible connections in and connections out.
Discard any words that have 0 ins and 0 outs.
Identify an initial set of "starter words" with the lowest numbers of ins and outs, and the outs must be greater than 0.
Each starter word receives its own working copy of the ins / outs connection count. This forms the head of the chain.
For each chain, identify a list of "next words" based upon:
- last letter of starter or previous word
- lowest number of of ins and outs connections (again, the outs must be greater than 0)
For each next word, repeat step 5 until the chain terminates.

Keep in mind that:

You'll need to keep track of the length of the chains and have some global mechanism to identify the longest chain.
You'll also need to remove each word from the working copy of the connection counts in order to avoid a recursive loop.
At some point, your chain will terminate and you have to select a word with a 0 connection out count.
You may have to recalculate ins / outs as words are removed from the working lists. At first glance, I don't think this will be necessary as the overall sets will be relatively small. If you scaled out to 1000 words, then having static counts may slow down the algorithm from converging.

I kind of saw this as a packing problem. To me, the connections in and out identify the shape to be packed. The lower the connections, the more odd the shape. The more odd the shape, the sooner I want to pack it as I perceived having decreasing odds of being able to pack an odd shape the later I got into the chain.

As an example:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

My first attempt:

Best Answer

Related Solutions

Algorithms – Possible Improvements to Damerau-Levenshtein Algorithm

Longest list of words with matching start and end letters

Related Topic