Question

The edit distance satisfies the axioms of a metric when the costs are non-negative.

(a) True

(b) False

This question was addressed to me in unit test.

Asked question is from Edit Distance Problem topic in division Dynamic Programming of Data Structures & Algorithms II

Answer 1

Correct option is (a) True

Easiest explanation - 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.