Minimum Edit Operations

Given two strings s and t, compute the minimum number of edit operations required to transform s into t. The allowed operations are insertion, deletion, and substitution (replacement) of a single character. Each operation has an associated cost of 1.

In other words, find the minimum number of operations to convert s to t using the following recurrence relation:

$$dp[i][j] = \begin{cases} dp[i-1][j-1] & \text{if } s_i = t_j, \\ 1 + \min(dp[i-1][j],\; dp[i][j-1],\; dp[i-1][j-1]) & \text{otherwise.} \end{cases}$$

Here, dp[i][j] denotes the minimum edit distance between the first i characters of s and the first j characters of t.

inputFormat

The input consists of two lines. The first line contains the string s and the second line contains the string t.

Note: The strings can be empty.

outputFormat

Output a single integer representing the minimum number of operations required to convert s into t.

abc
acb

2