Re: [algogeeks] convert a string into another in minimum number of steps
Yes Edit Distance is Most Efficient Algorithms Implemented So far and we all know this :P , but Sukran is saying Trie ? seems odd initially but let me analyze it ,Seems Good to me but we need to store length of strings in advance so that while inserting in trie wherever 1st mismatch occurs , we can just subtract current index from length of matching sting isn't it ? for map & man assume map is already in trie , when we try to insert man in try mismatch occurs at index 2 & length of "man" is 3 so number of steps required to convert is 1only Time Complexity for both search & insert both are constant using Trie O(K) where K is length of String which is again constant its an approach , may contains bug , let me know if missed something? 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/-/-ecPCKH4egcJ. 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.
Re: [algogeeks] convert a string into another in minimum number of steps
So the intermediate words need not be dictionary words? Karthik R, R&D Engineer, Tejas Networks. On Tue, Aug 30, 2011 at 11:50 AM, PRATEEK VERMA wrote: > edit distance algorithm -- 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.
Re: [algogeeks] convert a string into another in minimum number of steps
Anup has proposed good solution.use edit distance algorithm and make matrix for insertion and deletion operation. Last entry of the matrix will give the solution which says about minimum possible operation to convert one string to other. -- 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.
Re: [algogeeks] convert a string into another in minimum number of steps
This is more like a graph traversal problem. All the dictionary words form the nodes, strings who differ by one digit have edges between them. What is the shortest path from Node "map" to Node "man". Here it will be 1 as man and map have a edge between them. Karthik R, R&D Engineer, Tejas Networks. On Tue, Aug 30, 2011 at 11:25 AM, Anup Ghatage wrote: > Possibly a case of finding the longest common sub-sequence and then doing > the insertions/deletions etc > or AKA Levenshtein distance / Edit Distance > -- > Anup Ghatage > > -- > 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. > -- 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.
Re: [algogeeks] convert a string into another in minimum number of steps
Possibly a case of finding the longest common sub-sequence and then doing the insertions/deletions etc or AKA Levenshtein distance / Edit Distance -- Anup Ghatage -- 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.
[algogeeks] convert a string into another in minimum number of steps
convert a string into another in minimum number of steps. insertion of a new character , deletion will be considerd as a step. for ex. to convert "map" into man requires 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.
