Minimum Edit Distance

Given two strings str1 and str2, determine the minimum number of operations required to convert one string into the other. An operation is defined as inserting, deleting, or replacing a character.

The problem can be solved using dynamic programming. Let \(dp[i][j]\) denote the minimum edit distance between the first \(i\) characters of str1 and the first \(j\) characters of str2. The recurrence relation is given by:

\(dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 \\ dp[i][j-1] + 1 \\ dp[i-1][j-1] + \begin{cases} 0, & \text{if } str1[i-1] = str2[j-1] \\ 1, & \text{otherwise} \end{cases} \end{cases}\)

Your task is to implement this algorithm and output the minimum number of operations required.

inputFormat

The input is given from standard input (stdin) and consists of three lines:

1. The first line contains two integers \(N\) and \(M\), the lengths of str1 and str2 respectively.
2. The second line contains the string str1.
3. The third line contains the string str2.

outputFormat

Output to standard output (stdout) a single integer, the minimum edit distance required to convert str1 to str2.

6 5
abcdef
azced

3