Solution using Tabulation and Memoization


#1

Tabulation:

int min(int x, int y, int z)
{
return min(min(x,y),z);
}

int Solution::minDistance(string A, string B) {

int m = A.size();
int n = B.size();

int dp[m+1][n+1];

for(int i = 0; i<=m; ++i) dp[i][0] = i;
for(int i = 0; i<=n; ++i) dp[0][i] = i;

for(int i = 1; i<=m; ++i)
{
    for(int j = 1; j<=n; ++j)
    {
        if(A[i-1]==B[j-1]) dp[i][j] = dp[i-1][j-1];
        else
        {
            dp[i][j] = 1 + min(dp[i-1][j] , dp[i][j-1], dp[i-1][j-1]);
        }
    }
}
return dp[m][n];

}

Memoization:

int min(int x, int y, int z)
{
return min(min(x,y),z);
}

int edit_distance(int m, int n, string s1, string s2, vector<vector>& dp)
{
if(m==0)
{
dp[m][n] = n;
return n;
}
if(n==0)
{
dp[m][n] = m;
return m;
}
if(dp[m][n]!=-1) return dp[m][n];
if(s1[m-1]==s2[n-1])
{
dp[m][n] = edit_distance(m-1,n-1,s1,s2,dp);
return dp[m][n];
}
else
{

    dp[m][n] =  1 + min( edit_distance(m,n-1,s1,s2,dp),
                    edit_distance(m-1,n,s1,s2,dp),
                    edit_distance(m-1,n-1,s1,s2,dp));
    return dp[m][n];
}

}

class Solution
{
public:
int minDistance(string A, string B){

int m = A.size();
int n = B.size();

vector<vector<int>> dp(m+1,vector<int>(n+1,-1));    



return edit_distance(m,n,A,B,dp);

}
};


#2

memoization is not working it shoe redeclaration of class solution provide help how to run the memozied code