Edit Distance

Given two strings A and B, find the minimum number of steps required to convert A to B. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

The first argument of input contains a string, A.
The second argument of input contains a string, B.

Return an integer, representing the minimum number of steps required.

1 <= length(A), length(B) <= 450

Input 1:
    A = "abad"
    B = "abac"

Output 1:
    1

Explanation 1:
    Operation 1: Replace d with c.

Input 2:
    A = "Anshuman"
    B = "Antihuman"

Output 2:
    2

Explanation 2:
    => Operation 1: Replace s with t.
    => Operation 2: Insert i.

Method:

   M[i][j] = min ( 1 + M[i - 1][j - 1] replace, 1 + M[i - 1][j] delete, 1 + M[i][j - 1] insert
                          replace A[i - 1]                delete A[i - 1]         insert B[j - 1]
        
                   if i != j
                   else
                   M[i - 1][j - 1]        

Solution:

Time: O(mn)
Space: O(mn)

public class Solution {
    public int minDistance(String A, String B) {      
        int m = A.length();
        int n = B.length();
        if (m == 0) return n;
        if (n == 0) return m;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i <= m; i ++) {
            for (int j = 0; j <= n; j ++) {
                if (i == 0 && j == 0) {
                    dp[i][j] = 0;
                } else if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
                }
            }
        }
        return dp[m][n];
    }
}