CODEWITHSUNDEEP
stringalgorithmlevenshtein-distanceedit-distance
Min
Min

Reputation: 528

Levenshtein edit distance and different sets of edits

I was just going over some questions but I got stuck at a Levenshtein edit distance question.

So the first part of the question was:

What is the Levenshtein edit distance between the strings STRONGEST and TRAINERS?

Which I calculated as 6. But the next question I could not get is

Let d be the edit distance found in part (so 6). How many different sets of d ‘edits’ (insertions, deletions, or substitutions) are there that will change the string STRONGEST into the string TRAINERS?

Could anyone explain how I could find how many different sets exists here and how you arrived with the solution?

Upvotes: 1

Views: 820

Answers (1)

Gaurav Singh
Gaurav Singh

Reputation: 456

If you have used memoization table approach for the first problem, just go to the right-bottom corner of table (where you get minimum edit distance) and trace back all possible paths of minimum edits. All these paths will give you different sets of edits. For reference on how to trace back, you could see this solution to problem of printing LCS of two strings.

You could also refer to my comment on the above mentioned page.

Upvotes: 1

Related Questions