LC 0072 [H] Edit Distance (Levenshtein Distance) - ALawliet/algorithms GitHub Wiki

replace forces a match so they both move both pointers but replace costs 1 operation whereas match does not

if w1[i] == w2[j]: # no operation
  (i+1, j+1)
else: # +1 operation
  insert: (i, j+1)
  delete: (i+1, j)
  replace: (i+1, j+1)

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        ROWS = len(word1)
        COLS = len(word2)

        # a 2d array of word1 and word2 with +1 padding for the empty string
        # each cell represents the subproblem of the substrings at [i][j] and solves the min edit distance so far
        T = [ [0 for c in range (COLS + 1)] for r in range(ROWS + 1) ]
        
        # if we compare the empty string and [i][0] or [0][j], it's a +1 insert every time, so we can pre-fill with the index
        for r in range(ROWS + 1):
            T[r][0] = r
        for c in range(COLS + 1):
            T[0][c] = c
                    
        for r in range(1, ROWS + 1):
            for c in range(1, COLS + 1):
                # [match|replace][insert]
                # [delete]
                match = replace = T[r-1][c-1] ; insert = T[r][c-1]
                delete  = T[r-1][c]
                
                # -1 cause padding
                # the cost of match is the cost as if we pretend those chars weren't there
                # they don't incur a cost because they are the same
                if word1[r-1] != word2[c-1]:
                    T[r][c] = min(replace, delete, insert) + 1
                else:
                    T[r][c] = match + 0
                    
        # print(T)
        
        return T[-1][-1]
    
'''
f(m,n) = Edit distance between x1...xm and y1...yn = 
{
    f(m-1,n) + 1
    f(m,n-1) + 1
    f(m-1,n-1) + s
        s = 0 if xm = yn
            1 otherwise
}
'''