Given a string S and a string T, count the number of distinct subsequences of S which equals T.

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

Example 1:


Input: S = "rabbbit", T = "rabbit"
Output: 3
Explanation:

As shown below, there are 3 ways you can generate "rabbit" from S.
(The caret symbol ^ means the chosen letters)

rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^


Example 2:


Input: S = "babgbag", T = "bag"
Output: 5
Explanation:

As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
  ^  ^^
babgbag
    ^^^

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Starter code: class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        

Solutions:
class Solution:

	def numDistinct(self, s, t):
		setOft = set(t)
		news = ''
		for ch in s:
			if ch in setOft:
				news += ch
		dp = [[1 for i in range(len(news) + 1)] for j in range(len(t) + 1)]
		for j in range(1, len(t) + 1):
			dp[j][0] = 0
		for i in range(len(t)):
			for j in range(len(news)):
				if t[i] == news[j]:
					dp[i + 1][j + 1] = dp[i][j] + dp[i + 1][j]
				else:
					dp[i + 1][j + 1] = dp[i + 1][j]
		return dp[len(t)][len(news)]


class Solution:

	def __init__(self):
		self.dp = {}
		self.s = ''
		self.t = ''
		self.letter2Indices = {}

	def numDistinct(self, s, t):
		if len(s) < len(t):
			return 0
		if not t:
			return 1
		self.s = s.lower()
		self.t = t.lower()
		length = len(s)
		for i in range(len(t)):
			self.dp[i] = [-1] * length
		for i in range(length):
			letter = self.s[i]
			if letter in self.letter2Indices:
				self.letter2Indices[letter].append(i)
			else:
				self.letter2Indices[letter] = list([i])
		return self.numSubseq(0, 0)

	def numSubseq(self, startS, startT):
		if startT >= len(self.t):
			return 1
		if startS >= len(self.s):
			return 0
		if self.dp[startT][startS] >= 0:
			return self.dp[startT][startS]
		letter = self.t[startT]
		count = 0
		firstMatch = -1
		if letter in self.letter2Indices:
			for i in self.letter2Indices[letter]:
				if i >= startS:
					count += self.numSubseq(i + 1, startT + 1)
					if firstMatch < 0:
						firstMatch = i
		self.dp[startT][startS] = count
		for i in range(startS + 1, firstMatch):
			self.dp[startT][i] = count
		return count


class Solution:

	def numDistinct(self, s, t):
		result = (len(t) + 1) * [0]
		result[0] = 1
		for j in range(len(s)):
			for i in reversed(range(len(t))):
				if s[j] == t[i]:
					result[i + 1] += result[i]
		return result[-1]


class Solution:

	def numDistinct(self, s, t):
		row = len(s) + 1
		col = len(t) + 1
		dp = [0] * col
		dp[0] = 1
		for i in range(1, row):
			pre = dp[:]
			for j in range(1, col):
				if s[i - 1] == t[j - 1]:
					dp[j] += pre[j - 1]
		return dp[-1]


class Solution:

	def numDistinct(self, s, t):
		if len(s) < len(t):
			return 0
		dp = [0] * len(s)
		for i in range(len(s)):
			dp[i] = dp[i - 1] if i > 0 else 0
			if s[i] == t[0]:
				dp[i] += 1
		for (i, ti) in enumerate(t[1:]):
			dp2 = [0] * len(s)
			for j in range(i + 1, len(s)):
				dp2[j] = dp2[j - 1]
				if s[j] == ti:
					dp2[j] += dp[j - 1]
			dp = dp2
		return dp[-1]