Edit Distance Calculation

Given two strings s1 and s2, your task is to compute the edit distance between them. The edit distance is defined as the minimum number of operations required to convert s1 into s2 using the following allowed operations:

• Insertion
• Deletion
• Substitution

The recurrence relation of the edit distance is given by:

$$ dp(i,j) = \begin{cases} i & \text{if } j=0,\\[5pt] j & \text{if } i=0,\\[5pt] dp(i-1,j-1) & \text{if } s1[i-1] = s2[j-1],\\[5pt] 1 + \min\{dp(i-1,j),\, dp(i,j-1),\, dp(i-1,j-1)\} & \text{otherwise.} \end{cases} $$

You are required to read two strings from the standard input and print the edit distance to the standard output.

inputFormat

The input consists of two lines:

• The first line contains the string s1.
• The second line contains the string s2.

outputFormat

Output a single integer — the minimum number of operations required to convert s1 to s2.

abc
abc

0