-
April 5th, 2009, 04:18 PM
#1
C++: Convert Jumple Word to Possible Words
Hi,
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.
Current Algorithm
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 :-) )
Thanks
Varun
-
April 6th, 2009, 06:53 AM
#2
Re: C++: Convert Jumple Word to Possible Words
Off the top of my head...
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...
"A"
"B"
"I"
...
"AB"
"AI"
...
etc
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).
Edit:
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.
-
April 6th, 2009, 09:42 AM
#3
Re: C++: Convert Jumple Word to Possible Words
-
May 3rd, 2014, 06:48 AM
#4
Re: C++: Convert Jumple Word to Possible Words
Thanks for the link buddy.
-
May 4th, 2014, 03:33 AM
#5
Re: C++: Convert Jumple Word to Possible Words
Originally Posted by vsha041
If the input word / string is LARBITNLI, then the output should be TILL, TRILL and BRILLIANT.
I assume TILL, TRILL and BRILLIANT are in the dictionary and they're selected because they can be composed from the letters of LARBITNLI. Lets call this property composability.
It's especially easy to check for composability when both strings are sorted. Then it can be done in O(N), where N is the number of letters in the input string. And from this follows that its advantagous to have a version of the dictionary where each words string is presorted in letter order.
So checking for composability is O(N) but since N is limited (to 9) this operation finishes in constant time that is O(1).
What remains is a sequential scan where each of the presorted word strings in the dictionary is compared for composability with the sorted input string. And that's an O(N) operation where N is the number of words.
It's possible to refine this further by also keeping the dictionary of presorted word strings sorted. Then the input string can be checked for composability with the dictionary as a whole in a binary search fashion. This reduces complexity to O(logN).
Last edited by zizz; May 4th, 2014 at 05:23 AM.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|