Easy To Understand CPP - Solution


#1
int mem[451][451];

int getCount(string A,string B,int indexA,int indexB){
    if(indexA==A.length()){
        return B.length()-indexB;
    }
    
    if(indexB==B.length()){
        return A.length()-indexA;
    }
    
    
    if(mem[indexA][indexB]!=-1){
        return mem[indexA][indexB];
    }
    
    if(A[indexA]==B[indexB]){
        return mem[indexA][indexB]=getCount(A,B,indexA+1,indexB+1);
    }
    else{
        int deleteOpr=getCount(A,B,indexA+1,indexB);
        int insertOpr=getCount(A,B,indexA,indexB+1);
        int replaceOpr=getCount(A,B,indexA+1,indexB+1);
        
        return mem[indexA][indexB]=1+min(deleteOpr,min(insertOpr,replaceOpr));
    }
}

int Solution::minDistance(string A, string B) {
    int x=A.size();
    int y=B.size();
    memset(mem,-1,sizeof(mem));
    return getCount(A,B,0,0);
}