You are not logged in. Please login at www.codechef.com to post your questions!

×

How do I approach this ?

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

asked 23 Jan '15, 23:09

nickzuck_007's gravatar image

3★nickzuck_007
191620
accept rate: 14%


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

link

answered 24 Jan '15, 00:05

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

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

(25 Jan '15, 22:30) nickzuck_0073★

@nickzuck_007 Happy to help.. :) You can anytime post here and ask for help.. :)

(25 Jan '15, 22:35) damn_me3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,359
×193
×188

question asked: 23 Jan '15, 23:09

question was seen: 2,514 times

last updated: 25 Jan '15, 22:35