Pyhton 3 Solution with explanation


#1

class Solution:
# @param A : string
# @param B : string
# @return an integer

#It is same as that of LCS but with little variation , same as LCS we compare elements 
#one by one
#1.starting comparing from last, if elements are same then we recure to string 1 less 
#than original(LCS(A,B,m-1,n-1)
#2.if not equal we have three options
    # (i)Insert: Insert an element at last in A(same as last element of B)
    # now the A size become (m+1) and size of B is (n),ignoring last character and recursively
    # solve for (m,n-1)
    
    #(ii) Remove : Remove an element from last of A,now S1 length will be (m-1) and 
    # B length is n and recursively solve for (m-1,n)
    
    #(iii)Replace : Replace last character of A (same as last character of B so that
    # last character in both strings are same), now A length is m and B length is n
    # Recursively solving for (m-1,n-1)
# Taking min of all three because minimum operations asked in question
#Below is DP solution
def LCS(self,A,B):
    m=len(A)
    n=len(B)
    L=[[None]*(n+1) for i in range(m+1)]
    for i in range(m+1):
        for j in range(n+1):
            if(i==0):
                L[i][j]=j
            elif(j==0):
                L[i][j]=i
            elif(A[i-1]==B[j-1]):
                L[i][j]=L[i-1][j-1]
            else:
                L[i][j]=1+(min(L[i][j-1],L[i-1][j],L[i-1][j-1]))
    return(L[m][n])
def minDistance(self, A, B):
    #A = "bbbaabaa"
    #B = "aababbabb"
    Z=self.LCS(A,B)
    return(Z)