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

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)).

(see also http://forums.sun.com/thread.jspa?th...78584&tstart=0 )

Thanks for the link buddy.

Quote:

---

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).