Question

What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?

(a) 1

(b) 2

(c) 3

(d) 4

This question was posed to me by my college director while I was bunking the class.

Origin of the question is Wagner-Fischer Algorithm in section Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right choice is (b) 2

Easy explanation - The string “abcd” can be changed to “acbd” by substituting “b” with “c” and “c” with “b”. Thus, the edit distance is 2.