CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5
  1. #1
    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. #2
    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. #3

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


  4. #4
    Join Date
    Apr 2009
    Posts
    16

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

    Thanks for the link buddy.

  5. #5
    Join Date
    Aug 2013
    Posts
    55

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

    Quote Originally Posted by vsha041 View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured