Code derived from BacktoBack SWE's explanation (with comments) [C++]


#1
int Solution::minDistance(string A, string B) {
    // aka The Levenshtein Distance - watch Back to Back SWE's vid
    // choose whether to insert, delete or replace based on cost of doing them
    
    // A is current and B is what we want as final string
    int n = A.size(); int m = B.size();
    int i = 0, j = 0;
    // first row and col is " "
    int mat[n+1][m+1] = {}; 
    memset(mat, 0, sizeof(mat));
    mat[0][0] = 0;
    // first row and col filled
    for(i = 1; i<=m; i++) mat[0][i] = i;
    for(j = 1; i<=n; i++) mat[j][0] = j;
    
    for(i = 1; i<=n; i++){
        for(j = 1; j<=m; j++){
            // if letters not same, 1+max(left, diag, top) ele of curr cell
            //as they represent (delete, replace, insert) costs respectively
            if(A[i-1] != B[j-1]) mat[i][j] = 1+min({mat[i][j-1], mat[i-1][j-1], mat[i-1][j]});
            else mat[i][j] = mat[i-1][j-1]; // if match, pick up left diag element's cost
        }
    }
    // return bottom right-est val of matrix
    return mat[n][m];
    
}