Edit Distance

• Time : $O(nm)$
• Space : $O(nm)$

int Solution::minDistance(string A, string B) {
    int dp[A.length() + 1][B.length() + 1];
    for(int i = 0; i <= A.length(); i++) dp[i][0] = i;
    for(int i = 0; i <= B.length(); i++) dp[0][i] = i;
    for(int i = 1; i <= A.length(); i++) {
        for(int j = 1; j <= B.length(); j++) {
            dp[i][j] = A[i-1] == B[j-1] ? dp[i-1][j-1] : 1 + min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]});
        }
    }
    return dp[A.length()][B.length()];
}