1. Make a trie of all dictionary words. 2.then run a loop for all characters of string 3.suppose start from I ,as I is a word in dictionary,"word found" then increment counter 4.Now counter comes to X,no word found 5.Now it comes to A,two word could start from A(A and AM) now run this loop till end of string or till you didn't find M if find M,then word is AM ,otherwise it's A.then increment counter for outer loop 6.counter comes to F,no word found 7.G,M,J so on(No word found) 8.then A, again inner loop would run till the end of string length or till u didn't find M. In this way I think we could find all valid words in dictionary time complexity would be O(n^3) n for outer loop,n for inner loop and n for searching in trie
On Sun, Apr 14, 2013 at 12:41 PM, rahul sharma <rahul23111...@gmail.com>wrote: > Suppose you are given a string IAMABOY > > and a dictionary then divide it into I AM A BOY if it is possible to break > form as many dictionary words from a string give....M able to solve it..but > how if we are given a string like IXAFGMJAHBDSOXDY. > > how can we form I AM A BOY..will be done in Opower(2,n)..for every > character we consider it and not and form 2 ways...plz anyone shre the code > for this approach...if the word is not a cotiguous subarray.. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to algogeeks+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/groups/opt_out. > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
