BinarySearch 0104 Unique Subsequences Equal to Target

Problem statement

https://binarysearch.com/problems/Unique-Subsequences-Equal-to-Target/

Solution

Equal to leetcode 0115. Distinct Subsequences.

Complexity

It i sO(mn) for time and space.

Code

class Solution:
    def solve(self, s, t):
        @lru_cache(None)
        def dp(i, j):
            if i == -1: return j == -1
            if j == -1: return j == -1
            return (dp(i-1, j) + (s[i] == t[j]) * dp(i-1, j-1)) % (10**9 + 7)
        
        if not t: return 0
        return dp(len(s) - 1, len(t) - 1)