Make delicious recipes!

Create all dictionary words from the given characters



Problem: Given a dictionary of words and some characters, find all the dictionary words which can be made from one or more of these characters.


Solution: Brute force may not be a very good idea here.
If given number of characters is 'k', then powerset of these characters would contain 2k strings.
Each string can have m! permutations (where m is the word length).
So, if each and every combination is tried, then it would be very inefficient.

Its order would be:
2k*k! + 2k-1*(k-1)! + 2k-2*(k-2)! + 21*1!
Needless to say that this does not look a very pretty order especially if this operation has to be done on more than one char-arrays.


A better approach would be to pre-process the dictionary itself.
This is just a one-time effort and chances of dictionary getting updated frequently should be remote.

1) Take each word in the dictionary and convert it into a char-array.
  a) Sort char-array, convert again to a string and store it as a key in a hash-map.
  b) Value of this hash-map is a list of original words that made up this key.


2) Now sort the input characters and create the powerset of these sorted characters.


3) For each element in the powerset, check its presence in the pre-processed dictionary.
   a) If present, then value for this key is the list of valid dictionary words.

    


Order of execution = O(2k) where k is the length of the input characters.





Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal