First approach : I think you can solve the above problem using Levenshtein Distance (edit distance which is basically no of operations required to transform word1 to word2) . Algo can be found here http://en.wikipedia.org/wiki/Levenshtein_distance
Second approach : Store the words in trie data structure and then do a BFS on trie to achieve the solution. Hope this helps!!! On Mon, Aug 15, 2011 at 10:08 PM, priya ramesh < love.for.programm...@gmail.com> wrote: > You are given a dictionary of all valid words. You have the following 3 > operations permitted on a word: delete a character, insert a character, > replace a character. Now given two words - word1 and word2 - find the > minimum number of steps required to convert word1 to word2. (one operation > counts as 1 step.) > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > 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. > -- Regards Rajeev N B <http://www.opensourcemania.co.cc> "*Winners Don't do Different things , they do things Differently"* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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.