72. Edit Distance

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n = len(word1), len(word2)
        # edge case:
        if not word1 or not word2:
            return m + n
        # create memo 
        cache = [[-1]*(n) for _ in range(m)]
        return self.match(word1,word2,0,0,cache)
        #return memo[-1][-1]
    
    def match(self,w1,w2,i,j,memo):
        # termination conditions: 3 cases 
        if i == len(w1) and j == len(w2):
            return 0
        if i == len(w1):
            return len(w2)-j
        if j == len(w2):
            return len(w1) -i
        # check memo
        if memo[i][j]==-1: # i,j not saved in memo
            # match: return memo[i][j]
            if w1[i] == w2[j]:
                res = self.match(w1,w2,i+1,j+1,memo)
            # not match 
            else:
                # 3 cases: 1. insert 2. delete 3. replace ; each operation +1 cost  
                insert = 1 + self.match(w1,w2,i,j+1,memo)
                delete = 1 + self.match(w1,w2,i+1,j,memo)
                replace = 1 + self.match(w1,w2,i+1,j+1,memo)
                # find min cost 
                res = min(insert, delete, replace)
            memo[i][j] = res
        
        return memo[i][j] 
        
            

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # time O(len1*len2)  space O(len1*len2)
        # 3 loops 
        m = len(word1)
        n = len(word2)
        table = [[0]*(n+1) for _ in range(m+1)]
        
        for i in range(1,m+1):
            table[i][0] = i
        for j in range(1,n+1):
            table[0][j] = j 
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if word1[i-1] == word2[j-1]:
                    table[i][j] = table[i-1][j-1]
                else:
                    table[i][j] = 1 + min(table[i-1][j],table[i][j-1],table[i-1][j-1])
                
        return table[-1][-1]