I have written a program, in which it will ask the user to enter a string of length exactly 9. I have got a dictionary file with me which contains over two hundred thousand words. My job is to output all the possible words between lengths 4 to 9 that can be formed. For example:-
If the input word / string is LARBITNLI, then the output should be TILL, TRILL and BRILLIANT. I have written the program but I think it is most inefficient program ever because it is taking too much time to finish. I never actually allowed to finish but since I put several print statements, I could see that it is printing out the correct possible words.
I am taking the first word of dictionary (for example:- APPLE) and then I am checking if the frequency of all 27 alphabets in APPLE is than or equal to the frequency of all 27 alphabets in LARBITNLI.
Is there any better algorithm out there ? ( definitely :-) )
Rework your dictionary such that each word is keyed by its spelling in alphabetical order. That is:
APPLE becomes AELPP
BRILLIANT becomes ABIILLNRT
Then you simply do the same to your input (in your example, it would be ABIILLNRT again), and check each ordered permutation. So...
This is O(2^N), but N is always 9, so it'll finish in 512 iterations without any optimizations (such as refusing a perm if it has no vowels or something).
When you said "Dictionary", I assumed you meant Hash Table, which means constant time lookup. If you didn't mean that, then I suggest you do that. If you can't for whatever reason, you'll have to binary search for each one, so runtime will be more like 512 * O(lg(N)).
Last edited by SlickHawk; April 6th, 2009 at 06:56 AM.