How do I approach this ?

help
, ,
1

There is a function getWord() which takes word as input and checks whether word is present in the dictionary.Given a long word as input find all the meaning full ( i.e getWord() is true ) that can be made from the given input .
Example : Input : antin
output : a , an , ant, tin, in.

I am not able to find any solution other than brute force …If you have one, please do share…It will be a great help.Please do mention the type of the problem also, so that I can start studying those type and their approach…THANKS A LOT

2

To answer you, the whole of the answer lies in what we call a “TRIE”. It is a data structure in which each node has multiple branches. We start from start node and explore all possible paths from it.

Something like this:

     start
    / \ \ \.. till z
   a   b c d..
  / \
 *b*   c.. till z
/
*c*

The start symbol has 26 nodes (we are dealing with characters here). Further all these 26 nodes have 26 nodes as child nodes of each. With each node is associated a boolean flag which if set to 1, denotes a meaningful word from the start till the node. That is, in the above tree, “ab” and “abc”, these two strings are meaningful. This manner a dictionary is implemented. So, to check some word exists in the dictionary you need to implement it this manner only. Now, searching for that word in dictionary takes O(N) time. Similarly, all possible implementations can be printed.

Refer these links:

I can explain it more completely, but I think these links along with visuals are more apt for more understanding. If you still want, just let me know. I’ll be happy to help. I have complete code of it with me, but it’s little long. You’ll find much better and clean implementations on these… :slight_smile:

3

@damn_me thanks a tonn man …that was great …Will see you if I face any problem while learning trie

4

@nickzuck_007 Happy to help… :slight_smile: You can anytime post here and ask for help… :slight_smile: