Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

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?

share|improve this question
2  
Please realize that memorizing algorithms isn't what the interviewer wants. The interviewer wants to see how you attack the problem. What questions you ask back and define the problem. If you don't know how to think through a problem you don't know, you are missing the point of the question. –  MichaelT Feb 28 '13 at 6:07
    
@MichaelT you are right, people would through some problem at you and check how do you ask the right questions, how do you come up with some kind of approach. I am in a initial stage in this process,currently I am looking at this question and I cant relate it to any of the other questions or algorithms that I have read, the best solution that I can come up with is a brute force one. But once some one comes up with a some suggestion of guide me , may be I would be able to get a different perspective on the problem –  flash Feb 28 '13 at 6:23
    
Nope. There is no other smart way besides the brute force algorithm when you have to go through the whole dictionary and analyze every word summing up inclusions of letters (if met) from the given sample. The fact that a dictionary is already sorted by the alphabet don't give you much in this case. Take this as a problem when you have to analyze an unknown set of data. What previous knowledge you could apply even knowing this is a dictionary of English language? And even then the solution will relate to the given dictionary but not to the language itself. –  SChepurin Feb 28 '13 at 7:59
2  
more suited to codegolf.stackexchange.com ? –  jmo21 Feb 28 '13 at 9:51
    
Not totally related, but you might be interested in Scott Young's scrabble implementation: scotthyoung.com/blog/2013/02/21/wordsmith –  Jonathan Feb 28 '13 at 10:15

3 Answers 3

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

  1. 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...}
    
  2. 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.

share|improve this answer
    
Nice solution. Very nice approach of creating a 'index' and then creating a sum for each dictionary word and returning the word with largest sum!. thanks –  goldenmean Feb 28 '13 at 11:47

I'd like to add to SF's solution a bit. Not sure if I am correct in my analysis, but anyway:

If your preprocessing is free (considering search will be done enough times) you can preprocess each word in a dict by producing for it an entity like the index SF mentioned. So each word becomes a number like

01000100011101.... (up to the last letter a set of words can consist of)

where each 1 represents if the word has this letter or not (let's skip the case where it has double or more for simplicity).

You can further arrange this transformed dict by the amount of different letters the word has, to start searching with ones that contain most letters and be able to cut off search early once you enter the range that can't posibly have more matches than you already have.

When iterating over each word of a dictionary (now reduced to numbers) you simply XOR this number with the number produced from the set of the letters you are looking for and calculate its hamming weight(the number of 1s) which is essentially what you are looking for.

https://en.wikipedia.org/wiki/Hamming_weight

As the size of input is always constant (the size of the alphabet instead of variable word size) it can be done efficiently with publicly available algos. This way you wont have to compare letters one by one. Dealing with double/triple letters can be done by augmenting structures I suppose.

share|improve this answer

Just want to provide an alternative solution. If the number of random letters is small, you can try to generate all different permutations of the letters and check whether the dictionary contains a permutation.

For example, if you only have 3 letters "a", "b" and "c".

All the permutations are "abc", "bca", "cab", "ab", "bc", "ac", "a", "b" and "c". You can go from the longest ones to the shortest and check whether the dict contains the word. It is more efficient when the dictionary is large and the number of random letters is small.

share|improve this answer
    
This doesn't appear to solve the problem. While it would generate 'walkng' for the original (a very large set to iterate over), it wouldn't identify that 'walking' is a word that scores 6. It also doesn't handle duplicates of the same letter. –  MichaelT Jun 15 at 16:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.