Python recursion+memorirization


#1

class Solution:

def minDistance(self, A, B):
    self.dct=[[None for i in range(len(B)+1)] for j in range(len(A)+1)]
    return self.check(list(A),list(B),len(A)-1,len(B)-1)
def check(self,A,B,i,j):

    if(i==-1 and j==-1):
        return 0
    if(i<0 and j>=0):
        return j+1
    if(i>=0 and j<0):
        return i+1

    if self.dct[i][j]!=None:
        return self.dct[i][j]
    if(A[i]==B[j]):
        self.dct[i][j]=0+self.check(A,B,i-1,j-1)
        return self.dct[i][j]
    else:
        initial=A[i]
        A[i]=B[j]
        val1=1+self.check(A,B,i-1,j-1)
        A[i]=initial
        A.insert(i+1,B[j])
        val2=1+self.check(A,B,i,j-1)
        A.pop(i+1)
        A.pop(i)
        val3=1+self.check(A,B,i-1,j)
        A.insert(i,initial)
        self.dct[i][j]=min(val1,val2,val3)
        return self.dct[i][j]