I Think Trie is suitable DS for this problem , its similar "Did You Mean" Feature of Google
Paste it in ur address bar http://www.google.com/#hl=en&source=hp&q=Thatwouldbefantastic&oq=Thatwouldbefantastic&aq=f&aqi=&aql=&gs_sm=e&gs_upl=546l546l0l841l1l1l0l0l0l0l234l234l2-1l1l0&bav=on.2,or.r_gc.r_pw.r_cp.&fp=565b9cf32c7e938&biw=1280&bih=854 we can assume that all valid words are already in Trie(dictionary ) or even if they are not we can pre-process them to make a valid dictionary (trie) ,during this we will mark every valid word we have inserted in trie as valid by boolean flag EOW(end of word), after this pre-processing phase, Now we will go through given string check for valid word exist or not in Trie if found we set space in given string & keep continuing this un till finished whole string. structure of trie struct node { char character; // character of the node bool eow; // indicates a complete word int prefixes; // indicates how many words have the prefix node* edge[52]; // references to all possible sons //only alphabates } *root; // trie root node correct me if any flaw in approach * Thanks Shashank Mani Computer Science Birla Institute of Technology Mesra* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Zdhpn8ant7cJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
