class Solution:
    '''
    Time Complexity: O(m * n)
    Space Complexity: O(m * n)
    Where, m is length of s1, n is length of s2.
    Dynamic Programming with memoization problem.
    '''
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
        @cache        
        def dp(i,j):
            if i >= len(s1):
                return sum([ord(c) for c in s2[j:]])
            if j >= len(s2):
                return sum([ord(c) for c in s1[i:]])
            if s1[i] == s2[j]:
                return dp(i+1,j+1)
            return min(ord(s1[i]) + dp(i+1,j), ord(s2[j]) + dp(i,j+1))
        return dp(0,0)