Edit Distance Problem in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

The line arr[i][j] = min completes the above code.

The empty string can be transformed into "abcd" by inserting "a", "b", "c" and "d" at appropriate positions. Thus, the edit distance is 4.

"monday" can be converted to "tuesday" by replacing "m" with "t", "o" with "u", "n" with "e" and inserting "s" at the appropriate position. So, the edit distance is 4.

Consider the strings "abcd" and "efghi". The string "efghi" can be converted to "abcd" by deleting "i" and converting "efgh" to "abcd". The cost of transformation is 5, which is equal to the length of the larger string.

The edit distance will be zero only when the two strings are equal.

All of the mentioned are the applications of the edit distance problem.

d(s,s) = 0, since each string can be transformed into itself without any change.

d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.

d(s1, s2) = d(s2, s1)

(d(s1, s3) <= d(s1, s2) + d(s2, s3))

Thus, the edit distance satisfies the axioms of a metric.

Both dynamic programming and recursion can be used to solve the edit distance problem.