1. Delete a character
2. Replace a character with another one
3. Insert a character
Strings don't contain spaces in between.
The first line of input contains the string 'S' of length 'N'.
The second line of the input contains the String 'T' of length 'M'.
The only line of output prints the minimum "Edit Distance" between the strings.
You do not need to print anything; it has already been taken care of. Just implement the given functions.
0 <= N <= 10 ^ 3
0 <= M <= 10 ^ 3
Time Limit : 1sec
We will use the dynamic programming approach here and will have a 2-dimensional array, dp where
dp[i][j] stores the edit distance of the (i+1)th length substring of str1 and (j+1)th length substring of str2 starting from index 0
The base case would be when the size of first-string is 0 then edit distance will be equal to the size of other string i.e when i = 0 then dp[i][j] = j and similarly vice versa, so if j = 0 then dp[i][j] = i.
Now we will use our recurrence relation
// If str1[i - 1] == str2[j - 1]
dp[i][j] = dp[i-1][j-1]
// Otherwise
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])