72. Edit Distance Min operations to convert string 1 to another

'''
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

You have the following three operations permitted on a word:

Insert a character
Delete a character
Replace a character



'''

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m=len(word1)
        n=len(word2)
        arr=[[None]*(n+1) for _ in range(m+1)]
        def find(i,j):
            op=float('inf')
            if i==m and j==n:
                return 0
            if i==m:
                return n-j
            if j==n:
                return m-i
            if arr[i][j]!=None:
                return arr[i][j]

            else:
                if word1[i]==word2[j]:
                    op=min(op,find(i+1,j+1))
                else:
                    #replace
                    op=min(op,1+find(i+1,j+1))
                    #delete
                    op=min(op,1+find(i+1,j))
                    #insert
                    op=min(op,1+find(i,j+1))
                arr[i][j]=op
                return op
        return find(0,0)