Minimum ASCII Delete Sum for Two Strings LeetCode solution in Python

1
# Runtime: 4020 ms (Top 5.03%) | Memory: 205.5 MB (Top 14.36%)
2
class Solution:
3
    def minimumDeleteSum(self, s1: str, s2: str) -> int:
4
        m, n, lookup = len(s1), len(s2), {}
5

6
        def fun(i, j):
7
            if (i, j) in lookup:
8
                return lookup[(i, j)]
9
            if i < 0:
10
                return sum([ord(char) for char in s2[: j + 1]])
11
            if j < 0:
12
                return sum([ord(char) for char in s1[: i + 1]])
13
            if s1[i] == s2[j]:
14
                res = fun(i - 1, j - 1)
15
            else:
16
                res = min(ord(s1[i]) + fun(i - 1, j), ord(s2[j]) + fun(i, j - 1))
17
            lookup[(i, j)] = res
18
            return lookup[(i, j)]
19

20
        return fun(m - 1, n - 1)