C++: Convert Jumple Word to Possible Words
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 3 of 3

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

  1. #1
    Join Date
    Apr 2009

    C++: Convert Jumple Word to Possible Words


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



  2. #2
    Join Date
    Mar 2009

    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

    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.

  3. #3

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

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

Azure Activities Information Page

Windows Mobile Development Center

Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


HTML5 Development Center