Shouldn’t the example matrix be
0 A B A B
0 1 1 1 1 1
A 0 1 1 2 2
B 0 0 1 1 3
Example animation for 2d is wrong. Take (i, j) = (2, 1) for example. Why is it ‘1’? You can’t make the substring ‘ab’ using only ‘a’ from s. Base case is correct for the first row but incorrect for the first column. You cannot make anything with the empty substring (apart from the empty substring).
Another solution that makes no sense.
This is an extremely difficult problem, and it is not made easier by the error-riddled description above.
Let dp[i][j] = number of ways to generate t[:j] from s[:i].
i and j run from 1 to the length of the strings.
dp[i-1][j] = ways to generate t[j] using first i-1 characters of s
dp[i-1][j] → ways we had only using i-1 characters in s. We always still have that.
but if the new character s[i] is equal to t[j], then all the ways to generate t[j-1] must
also be included, because we can just add on s[i] to all of them and get a new way.
So, the recurrence relation is:
dp[i][j] = dp[i-1][j] + (dp[i-1][j-1] if t[j] == s[i])
dp[0][j] is zero (not one as in the Algomonster diagram)
There are no ways to generate a string of any length using the null string.
dp[i][0] = 1 (correct in Algomonster)
There is one way to generate the null string from any number of letters.
But you can overwrite dp[i-1] with dp[i] to save space. So you initialize dp[j] as one if j>0
and zero for dp[0]. Then you can loop forwards in i and backwards in j.
def sequence_check(s: str, t: str) → int:
m = len(s)
n = len(t)
if m < n or min(m,n) == 0:
return 0
dp = [0 for i in range(-1,n)]
dp[-1] = 1
for i in range(m):
newchar = s[i]
for j in range(n-1,-1,-1):
dp[j] = dp[j] # Always at least this many ways using previous number of characters.
if t[j] == newchar:
dp[j] += dp[j-1] # for each way there was to generate the string one shorter,
# there is also now a new way to generate t[j]
return dp[n-1]