CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: C++: Convert Jumple Word to Possible Words

1. Junior Member
Join Date
Apr 2009
Posts
16

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

2. Junior Member
Join Date
Mar 2009
Posts
19

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.

3. Member
Join Date
Oct 2007
Posts
126

Re: C++: Convert Jumple Word to Possible Words

4. Junior Member
Join Date
Apr 2009
Posts
16

5. Banned
Join Date
Aug 2013
Posts
55

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.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•