Edit Distance [LeetCode 72]

EditDistance.py

# Reference : https://www.youtube.com/watch?v=AuYujVj646Q

class Solution:
    
    def minDistance(self, x: str, y: str) -> int:
        
        # Init
        n = len(x)
        m = len(y)
        
        # Base Case
        if n == 0 or m==0:
            return max(n, m)
        
        # Init
        t = [[0 for _ in range(m+1)] for _ in range(n+1)]
        
        # For first row base case
        for c in range(1,m+1):
            t[0][c] = c
        
        # For first col base case
        for r in range(1,n+1):
            t[r][0] = r
            
        # DP Solution
        for i in range(1,n+1):
            for j in range(1,m+1):
                
                # If character at index i of x and index j of y doesn't match,
                # one has to perform three operations. Below are the three
                # operations descibed w.r.t. recursion. We will add a cost
                # of 1 to each of this operation.
                # 1) Insert: to insert missing character from y to x, it is 
                #            be inserted at position i+1, so i doesn't decrement
                #            but j decrements, i.e, (i,j-1)
                # 2) Remove: to remove a mismatch charater from x, it is removed
                #            at position i, so i decrements and j doesn't, (i-1,j)
                # 3) Replace: to replace a mismatch character at index i in x, with
                #             the character at index j in y, once replaced, both
                #             i and j decrements, i.e., (i-1,j-1)
                if x[i-1] != y[j-1]:
                    t[i][j] = min(t[i][j-1]+1, t[i-1][j]+1, t[i-1][j-1]+1)
                    
                # If character at index i of x and index j of y matches,
                # no operations will be performed, so in actual recursion
                # we will decrement both i and j and hence the value of
                # current position (i,j) depends on its previous position
                # (i-1,j-1)
                else:
                    t[i][j] = t[i-1][j-1]
        
        # Return the final result
        return t[n][m]