Edit Distance Problem

Given two strings A and B consisting only of lowercase letters, compute the minimum number of operations required to convert A into B. The allowed operations are:

1. Delete a character;
2. Insert a character;
3. Replace a character with another character.

This problem is a classic example of dynamic programming where the solution is computed using the edit distance algorithm, formulated as:

$$\text{dp}[i][j] = \min\begin{cases} \text{dp}[i-1][j] + 1,\\ \text{dp}[i][j-1] + 1,\\ \text{dp}[i-1][j-1] + \left[ A[i] \neq B[j] \right] \end{cases}$$

inputFormat

The first line contains the string A. The second line contains the string B.

outputFormat

Output a single integer representing the minimum number of operations required to transform A into B.

sample

abc
abc

0

</p>