Question115 Distinct subsequences

Link:

Code:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        IndexDict = dict()
        M = len(s)
        N = len(t)
        def UniqueSubsequence(i,j):
            if (i,j) in IndexDict:
                return IndexDict[i,j]
            else:
                if i == M or j == N or M-i<N-j:
                    return int(j == N)
                else:
                    if (i,j) in IndexDict:
                        return IndexDict[i,j]
                    else:
                        ans = UniqueSubsequence(i+1,j)
                        if s[i] == t[j]:
                            ans += UniqueSubsequence(i+1,j+1)
                        IndexDict[i,j] = ans
                        return ans
        
                        
                        
        return UniqueSubsequence(0,0)