<p>Given two strings s and t, return <i>the number of distinct</i> <b><i>subsequences</i></b><i> of </i>s<i> which equals </i>t.</p>

<p>The test cases are generated so that the answer fits on a 32-bit signed integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;rabbbit&quot;, t = &quot;rabbit&quot;
<strong>Output:</strong> 3
<strong>Explanation:</strong>
As shown below, there are 3 ways you can generate &quot;rabbit&quot; from s.
<code><strong><u>rabb</u></strong>b<strong><u>it</u></strong></code>
<code><strong><u>ra</u></strong>b<strong><u>bbit</u></strong></code>
<code><strong><u>rab</u></strong>b<strong><u>bit</u></strong></code>
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;babgbag&quot;, t = &quot;bag&quot;
<strong>Output:</strong> 5
<strong>Explanation:</strong>
As shown below, there are 5 ways you can generate &quot;bag&quot; from s.
<code><strong><u>ba</u></strong>b<u><strong>g</strong></u>bag</code>
<code><strong><u>ba</u></strong>bgba<strong><u>g</u></strong></code>
<code><u><strong>b</strong></u>abgb<strong><u>ag</u></strong></code>
<code>ba<u><strong>b</strong></u>gb<u><strong>ag</strong></u></code>
<code>babg<strong><u>bag</u></strong></code></pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length, t.length &lt;= 1000</code></li>
	<li><code>s</code> and <code>t</code> consist of English letters.</li>
</ul>

'''
Given two strings s and t, return the number of distinct subsequences of s which equals t.

logically 
at each index in the string s -> we can either include the letter in our substirng 
or we can pass it

from the first letter we can either include it in our substring or we can pass it
if it is the same letter -> and we choose to include it
-> we shift index for t by 1 to the right
if we choose not to include it we can keep the same t index while shifting s index to the right (or left) whichever is decided

'''
class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        memo = {}
        m = len(s)
        n = len(t)

        def findWays(m , n):
            if n == 0:
                return 1 
            if m == 0:
                return 0
            if (m, n) in memo:
                return memo[(m, n)]
            
            if s[m - 1] == t[n - 1]:
                take = findWays(m - 1, n - 1) 
                avoid = findWays(m - 1, n)
                memo[(m, n)] = take + avoid
            else:
                avoid = findWays(m - 1, n)
                memo[(m, n)] = avoid
            
            return memo[(m, n)]
        
        return findWays(m, n)
            

136248