 # 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)``````