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, no registration required.

Given some random letters , For example "a,e,o,g,z,k,l,j,w,n" and a dictionary.Try to find a word in the dictionary that has most letters given

I was going through some old interview questions and found this question, I am new to algorithms and I am thinking whether this can be related to dynamic programming(Longest common subsequence)

this is the solution that I can think of

"Let us assume that the dictionary is in a trie 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."

I tried searching online but could not find any example that match this could you provide some pointers.

share|improve this question
1  
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 ? –  Ozz 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
show 3 more comments

1 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

  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
add comment

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.