title: Calculating Minimum Edit Distance for unequal strings python
body: <p>I am trying to implement Minimum Edit Distance with the substitution cost of 2. Following is the code I've so far. It works well for strings of equal length but generates error for the unequal strings. Kindly correct me where i am wrong</p>
  
  <pre><code>def med(source, target):
  #     if len(x) &gt; len(y):
  #         print("insode if")
  #         source, target = y, x
  print(len(source), len(target))
  cost = [[0 for inner in range(len(source)+1)] for outer in 
  range(len(target)+1)]
  
  global backtrace 
  backtrace = [[0 for inner in range(len(source)+1)] for outer in 
  range(len(target)+1)]
  global SUB
  global INS
  global DEL
  
  for i in range(0,len(target)+1):
      cost[i][0] = i
  
  for j in range(0,len(source)+1):
      cost[0][j] = j
  
  for i in range(1,len(target)+1):
      for j in range(1,len(source)+1):
          if source[i-1]==target[j-1]:
              cost[i][j] = cost[i-1][j-1] 
          else:
              deletion = cost[i-1][j]+1
              insertion = cost[i][j-1]+1
              substitution = cost[i-1][j-1]+2
              cost[i][j] = min(insertion,deletion,substitution)
  
              if cost[i][j] == substitution:
                  backtrace[i][j] = SUB
              elif cost[i][j] == insertion:
                  backtrace[i][j] = INS
              else:
                  backtrace[i][j] = DEL
  
  
  return cost[i][j]
  
  med("levenshtein","levels")
  </code></pre>
  
  <p>The error i get is:</p>
  
  <pre><code>---------------------------------------------------------------------------
  IndexError                                Traceback (most recent call last)
  &lt;ipython-input-26-86bf20ea27c7&gt; in &lt;module&gt;()
   49     return cost[i][j]
   50 
  ---&gt; 51 med("levenshtein","levels")
  
  &lt;ipython-input-26-86bf20ea27c7&gt; in med(source, target)
   31     for i in range(1,len(target)+1):
   32         for j in range(1,len(source)+1):
  ---&gt; 33             if source[i-1]==target[j-1]:
   34                 cost[i][j] = cost[i-1][j-1]
   35             else:
  
  IndexError: string index out of range
  </code></pre>