Question

Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.

(a) True

(b) False

The question was asked during a job interview.

My enquiry is from Edit Distance Problem topic in portion Dynamic Programming of Data Structures & Algorithms II

Answer 1

Right option is (a) True

The explanation is: 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.