edit distance

'''
LCS variation:
if the character matches, then look for next characters
if the character doesn't match, there are 3 possibilties, given you can do all the operations on the s1 only:
    insert: you can insert the mth of s2 character and then look for the next characters so insertion happened at n+1 with the mth character so n+1-1, m-1 ie (n,m-1)
    delete: you can delete the nth character of s1 so after deletion indices (n-1,m) as the nth character you deleted and mth character will match with the remaining string
    replace: you can replace the mth character with nth character so now nth and mth character mathcing, so you can move ahead and skip nth and mth character.


Base case:
if n<0-> it means s1 is finished so you will have to insert the remaining characters of the s2 to match ie. m+1
if m<0-> it means s2 is finished so you will have to delete the reamining characters of the s1 to match ie. n+1
'''
def fun(s1,s2,n,m,dp):
    if n<0: #s1 is finished so to match, we must insert m+1 char of s2 in beginning
        return m+1
    if m<0: #s2 is finished so to match, we must delete all n+1 character of s1 in the beginning
        return n+1
    if dp[n][m]!=-1:
        return dp[n][m]

    if s1[n]==s2[m]:
        dp[n][m]=fun(s1,s2,n-1,m-1,dp)
    else:
        insert=1+fun(s1,s2,n,m-1,dp)
        delete=1+fun(s1,s2,n-1,m,dp)
        replace=1+fun(s1,s2,n-1,m-1,dp)
        dp[n][m]=min([insert,delete,replace])
    return dp[n][m]

class Solution:
    def minDistance(self, s1: str, s2: str) -> int:
        dp=[[-1]*len(s2) for _ in range(len(s1))]
        return fun(s1,s2,len(s1)-1,len(s2)-1,dp)