Problem statement

https://binarysearch.com/problems/Edit-Distance-Sequel/

Solution

First of all, it is not obvious in which way we need to return answer, there is no explanation about it in statement, only in examples! What we actually need to do is to start with the first symbol and return operations we need to do. Let dp(i, j) be the answer for subproblem W1[i:] and W2[j:]. Then we need to recunstruct answer.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, W1, W2):
        l1, l2 = len(W1), len(W2)
        
        @lru_cache(None)
        def dp(i, j):
            if i == l1 and j == l2: return 0
            if i > l1 or j > l2: return float("inf")
            if i < l1 and j < l2 and W1[i] == W2[j]: return 1 + dp(i + 1, j + 1)
            return min(dp(i + 1, j), dp(i, j + 1)) + 1
        
        i, j, ans = 0, 0, []
        while i < l1 or j < l2:
            if i < l1 and j < l2 and W1[i] == W2[j]:
                ans += [W1[i]]
                i, j = i + 1, j + 1
            elif i < l1 and dp(i, j) == dp(i + 1, j) + 1:
                ans += ["-" + W1[i]]
                i += 1
            else:
                ans += ["+" + W2[j]]
                j += 1

        return ans