Edit Distance Python

PROGRAM TO FIND MINIMUM NUMBER OF EDITS REQUIRED TO CONVERT STRING

def minDis(s1, s2, n, m, dp) :

          

  # If any string is empty,

  # return the remaining characters of other string         

  if(n == 0) :

      return m       

  if(m == 0) :

      return n

                    

  # To check if the recursive tree

  # for given n & m has already been executed

  if(dp[n][m] != -1)  :

      return dp[n][m];

                   

  # If characters are equal, execute

  # recursive function for n-1, m-1   

  if(s1[n - 1] == s2[m - 1]) :          

    if(dp[n - 1][m - 1] == -1) :

        dp[n][m] = minDis(s1, s2, n - 1, m - 1, dp)

        return dp[n][m]                  

    else :

        dp[n][m] = dp[n - 1][m - 1]

        return dp[n][m]

         

  # If characters are nt equal, we need to          

  # find the minimum cost out of all 3 operations.        

  else :           

    if(dp[n - 1][m] != -1) :  

      m1 = dp[n - 1][m]     

    else :

      m1 = minDis(s1, s2, n - 1, m, dp)

              

    if(dp[n][m - 1] != -1) :               

      m2 = dp[n][m - 1]           

    else :

      m2 = minDis(s1, s2, n, m - 1, dp)  

    if(dp[n - 1][m - 1] != -1) :   

      m3 = dp[n - 1][m - 1]   

    else :

      m3 = minDis(s1, s2, n - 1, m - 1, dp)

     

    dp[n][m] = 1 + min(m1, min(m2, m3))

    return dp[n][m]

     

    # Driver code

str1 = "voldemort"

str2 = "dumbledore"

    

n = len(str1)

m = len(str2)

dp = [[-1 for i in range(m + 1)] for j in range(n + 1)]

              

print(minDis(str1, str2, n, m, dp))




OUTPUT:

7

CREDITS: https://www.geeksforgeeks.org/count-number-binary-strings-without-consecutive-1s/