115. Distinct Subsequences #

Problem #

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

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

It is guaranteed the answer fits on a 32-bit signed integer.

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbitrabbbitrabbbit

Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
babgbagbabgbagbabgbagbabgbagbabgbag

Constraints:

0 <= s.length, t.length <= 1000
s and t consist of English letters.

Problem Summary #

Given a string s and a string t, calculate the number of times t appears among the subsequences of s. A subsequence of a string is a new string formed by deleting some characters (or none) without disturbing the relative positions of the remaining characters. (For example, “ACE” is a subsequence of “ABCDE”, while “AEC” is not.) The problem data guarantees that the answer fits within the range of a 32-bit signed integer.

Solution Approach #

How many strings t can be contained in the string s at most. This contains many overlapping subproblems, so try to solve this problem with dynamic programming. Define dp[i][j] as the number of times t[j:] appears among the subsequences of s[i:]. For initialization, first consider the boundary conditions. When i = len(s) and 0≤ j < len(t), s[i:] is an empty string and t[j:] is not empty, so dp[len(s)][j] = 0. When j = len(t) and 0 ≤ i < len(s), t[j:] is an empty string, and the empty string is a subsequence of any string. So dp[i][n] = 1.
When i < len(s) and j < len(t), if s[i] == t[j], there are 2 matching methods. The first is to match s[i] with t[j], then t[j+1:] matches a subsequence of s[i+1:], and the number of subsequences is dp[i+1][j+1]; the second is not to match s[i] with t[j], and t[j:] is treated as a subsequence of s[i+1:], with the number of subsequences being dp[i+1][j]. Combining the 2 cases, when s[i] == t[j], dp[i][j] = dp[i+1][j+1] + dp[i+1][j].
If s[i] != t[j], then t[j:] can only be a subsequence of s[i+1:], and the number of subsequences is dp[i+1][j]. So when s[i] != t[j], dp[i][j] = dp[i+1][j]. In summary, we get:
\[ dp[i][j] = \left\{\begin{matrix}dp[i+1][j+1]+dp[i+1][j]&,s[i]=t[j]\\ dp[i+1][j]&,s[i]!=t[j]\end{matrix}\right. \]
Finally, the optimized version. After writing the above code, you can see that the table-filling process goes from the bottom-right corner all the way to the top-left corner. The table-filling order is row by row from bottom to top. Within each row, fill from right to left. Therefore, this two-dimensional data can be compressed into one dimension. Because filling the current row only needs information from the next row, and more specifically, it uses information from the elements to the right in the next row. Therefore, each time this row is updated, first store the old value, and when calculating the update for this row, update from right to left. Doing this can reduce one dimension of space and compress the original two-dimensional array into a one-dimensional array.

Code #

package leetcode

// Solution 1: Compressed DP
func numDistinct(s string, t string) int {
	dp := make([]int, len(s)+1)
	for i, curT := range t {
		pre := 0
		for j, curS := range s {
			if i == 0 {
				pre = 1
			}
			newDP := dp[j+1]
			if curT == curS {
				dp[j+1] = dp[j] + pre
			} else {
				dp[j+1] = dp[j]
			}
			pre = newDP
		}
	}
	return dp[len(s)]
}

// Solution 2: Standard DP
func numDistinct1(s, t string) int {
	m, n := len(s), len(t)
	if m < n {
		return 0
	}
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][n] = 1
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s[i] == t[j] {
				dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
			} else {
				dp[i][j] = dp[i+1][j]
			}
		}
	}
	return dp[0][0]
}