title: Minimum Edit Distance Reconstruction
body: <p>I know there are similar answer to this on stack, as well as online, but I feel I'm missing something. Given the code below, we need to reconstruct the sequence of events that led to the resulting minimum edit distance. For the code below, we need to write a function that outputs:</p>
  
  <pre><code>Equal, L, L
  Delete, E
  Equal, A, A
  Substitute, D, S
  Insert, T
  </code></pre>
  
  <p><strong>EDIT: CODE IS UPDATED WITH MY (PARTIALLY CORRECT) SOLUTION</strong></p>
  
  <p>Here is the code, with my partial solution. It works for example I was given ("lead" -> "last"), but doesn't work for the example below ("hint" -> "isnt"). I suspect this is because the first character is equal, which is throwing off my code. Any tips or pointers in the right direction would be great!</p>
  
  <pre><code>def printMatrix(M):
          for row in M:
                  print row
          print
  
  def med(s, t):  
          k = len(s) + 1
          l = len(t) + 1
  
          M = [[0 for i in range(k)] for j in range(l)]
          MTrace = [["" for i in range(k)] for j in range(l)]
  
          M[0][0] = 0
  
  
          for i in xrange(0, k):
                  M[i][0] = i
                  MTrace[i][0] = s[i-1]
  
          for j in xrange(0, l):
                  M[0][j] = j
                  MTrace[0][j] = t[j-1]
  
          MTrace[0][0] = "DONE"
  
          for i in xrange(1, k):
                  for j in xrange(1, l):
  
                          sub = 1
                          sub_op = "sub"
                          if s[i-1] == t[j-1]:
                                  # equality
                                  sub = 0
                                  sub_op = "eq"
  
  
                          # deletion
                          min_value = M[i-1][j] + 1
                          op = "del"
                          if min_value &gt; M[i][j-1] + 1:
                                  # insertion
                                  min_value = M[i][j-1] + 1
                                  op = "ins"
                          if min_value &gt; M[i-1][j-1] + sub:
                                  # substitution
                                  min_value = M[i-1][j-1] + sub
                                  op = sub_op
  
  
                          M[i][j] = min_value
                          MTrace[i][j] = op                        
  
          print "final Matrix"
          printMatrix(M)
          printMatrix(MTrace)
  
  ############ MY PARTIAL SOLUTION
  
          def array_append(array,x,y):
              ops_string = MTrace[x][y]
              if ops_string == 'ins':
                  array.append(("Insert",MTrace[0][y]))
              elif ops_string == 'sub':
                  array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
              elif ops_string == 'eq':
                  array.append(("Equal",MTrace[x][0],MTrace[0][y]))
              elif ops_string == 'del':
                  array.append(("Delete",MTrace[x][0]))
  
  
          i = len(s)
          j = len(t)
  
          ops_array = []
          base = M[i][j]
          array_append(ops_array,i,j)
  
  
          while MTrace[i][j] != "DONE":
              base = M[i][j]
              local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
              if base == local_min:
                  i = i - 1
                  j = j - 1
                  array_append(ops_array,i,j)
              elif M[i][j-1] &lt; M[i-1][j]:
                  j = j -1
                  array_append(ops_array,i,j)
              elif M[i-1][j] &lt; M[i][j-1]:
                  i = i - 1
                  array_append(ops_array,i,j)
              else:
                  i = i - 1
                  j = j - 1
                  array_append(ops_array,i,j)
  
          print ops_array
  #########
  
          return M[k-1][l-1]      
  
  print med('lead', 'last')
  </code></pre>