# Python DP solution beats 100% with explanation.

• For this solution, I will use an example to explain.
Some observations can be found as follows:

1. For s="baabacba" & t="aba", in order to have a solution for the first 'a' in t, there must exists a 'a'.
As for the second 'a' in t, there must exists a 'a' prior to the second 'a' and a 'b' after the first 'a'.
2. The first 'b' in s is redundant event though t contains 'b'.
3. Suppose that s="aab" & t="ab", it is obvious that there are only 2 solutions, and that solution is based on the solutions of s="aa" & t="a".
If s="aabb" & t="ab", the result is twice the result of s="aa" & t="a".
Therefore, the result of a matching character is the current result adds up with the result of the element before.

Combining the observations above, here is the solution.

``````class Solution(object):
def numDistinct(self, s, t):
if not t:
return 1
nLen = len(t)
table = [0 for i in range(nLen + 1)]
idxes = dict()
table[-1] = 1
cur = 0
for i in range(len(s)):
if cur < nLen:
if t[cur] == s[i]:
if t[cur] not in idxes:
idxes[t[cur]] = [cur]
else:
idxes[t[cur]].append(cur)
cur += 1
if s[i] in idxes:
for j in idxes[s[i]][::-1]:
table[j] += table[j-1]
return table[nLen-1]
``````

table is the DP which stores the result of each iteration.
The last element is set to 1 for dealing with cur==0 condition.
Each element stores the result of corresponding element in t.
cur denotes the index of the largest possible matching element (+1).
idxes, a dict(), stores all indices (<= i) in s where char s[i] locates.

Here is a step by step result of how this solution goes.

``````s="baabacba", t="aba"
0123
initial, table =[0001]
i=0,            [0001] (cur==1)
i=1,            [1001] (cur==1) (add table[-1] to table[0])
i=2,            [2001] (cur==1) (add table[-1] to table[0])
i=3,            [2201] (cur==2) (add table[0] to table[1])
i=5,            [3221] (cur==3)
i=6,            [3521] (cur==3) (add table[0] to table[1])