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 ,
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,
RD Engineer,
Tejas Networks.
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
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
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