# Data Structure Questions and Answers-Edit Distance Problem

## Click on any option to know the CORRECT ANSWERS

 Question 1
Which of the following methods can be used to solve the edit distance problem?
 A Recursion B Dynamic programming C Both dynamic programming and recursion D None of the mentioned

Question 1 Explanation:
Both dynamic programming and recursion can be used to solve the edit distance problem.

 Question 2
The edit distance satisfies the axioms of a metric when the costs are non-negative.
 A True B False

Question 2 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.

 Question 3
Which of the following is an application of the edit distance problem?
 A Approximate string matching B Spelling correction C Similarity of DNA D All of the mentioned

Question 3 Explanation:
All of the mentioned are the applications of the edit distance problem.

 Question 4
In which of the following cases will the edit distance between two strings be zero?
 A When one string is a substring of another B When the lengths of the two strings are equal C When the two strings are equal D The edit distance can never be zero

Question 4 Explanation:
The edit distance will be zero only when the two strings are equal.

 Question 5
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