LC115 - Distinct Subsequences

Problem

Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer.

Example

Input: s = "rabbbit", t = "rabbit" Output: 3 Explanation: As shown below, there are 3 ways you can generate "rabbit" from s. ==rabb==b==it== ==ra==b==bbit== ==rab==b==bit==

Solution

Cached DFS

Intuitively, use two pointers, one for each string s and t to check whether or not t is a subsequence of s. More or less, we're just checking if s[i] is equal to t[j], and incrementing i and j, and if not, incrementing i to see if the next character is equal to t[j]. Time and space complexity of this approach is $O(m\cdot n)$.

def numDistinct(self, s: str, t: str) -> int:
	@cache
	def dfs(i, j):
		# end reached, 1 distinct value found
		if j == len(t):
			return 1
		# end of s reached without reaching t, no distinct value found
		if i == len(s):
			return 0

		tmp = dfs(i+1)
		if s[i] == t[j]:
			tmp += dfs(i+1, j+1)
		return tmp
		
	return dfs(0,0)