BinarySearch 0484 Shortest Common Supersequence

Problem statement

https://binarysearch.com/problems/Shortest-Common-Supersequence/

Solution

Equal to Leetcode 1092. Shortest Common Supersequence, but easier, because we do not need to reconstruct answer.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(self, str1, str2):
        m, n = len(str1), len(str2)
        
        @lru_cache(None)
        def dp(i, j):
            if i == -1: return j + 1
            if j == -1: return i + 1
            if str1[i] == str2[j]:
                return dp(i-1, j-1) + 1
            return min(dp(i-1, j), dp(i, j-1)) + 1

        return dp(m - 1, n - 1)