数据结构与算法之动态规划: LeetCode 115. 不同的子序列 (Ts版)

不同的子序列

• https://leetcode.cn/problems/distinct-subsequences/description/

描述

• 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。

示例 1

输入：s = "rabbbit", t = "rabbit"
输出：3

解释：
如下所示, 有 3 种可以从 s 中得到 “rabbit” 的方案。
rabbbit
rabbbit
rabbbit

示例 2

输入：s = "babgbag", t = "bag"
输出：5

解释：
如下所示, 有 5 种可以从 s 中得到 “bag” 的方案。
babgbag
babgbag
babgbag
babgbag
babgbag

提示：

• 1 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

Typescript 版算法实现

1 ) 方案1

function numDistinct(s: string, t: string): number {
    const m = s.length, n = t.length;
    if (m < n) {
        return 0;
    }
    const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0));
    for (let i = 0; i <= m; i++) {
        dp[i][n] = 1;
    }
    for (let i = m - 1; i >= 0; i--) {
        for (let 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];
};

2 ) 方案2：递归(无记忆化)

function numDistinct(s: string, t: string): number {
	const sLen = s.length, tLen = t.length
	
	function helper(i, j) {
		if (j < 0) return 1
		if (i < 0) return 0
		if (s[i] == t[j]) {
			return helper(i-1, j) + helper(i-1, j-1)
		}
        return helper(i-1, j)
	}
	return helper(sLen-1, tLen-1) 
}

• LeetCode 超时

3 ) 方案3：递归 (记忆化)

function numDistinct(s: string, t: string): number {
	const sLen = s.length, tLen = t.length, memo = new Array(sLen)
	for (let i = 0; i < sLen; i++) {
		memo[i] = new Array(tLen)
		for (let j = 0; j < tLen; j++) {
			memo[i][j] =  -1
		}
	}
	function helper(i, j) {
		if (j < 0) return 1
		if (i < 0) return 0
		if (memo[i][j] !=  -1) { 
			return memo[i][j]
		}
		if (s[i] == t[j]) {
			memo[i][j] = helper(i-1, j) + helper(i-1, j-1)
		} else {
			memo[i][j] = helper(i-1, j)
		}
		return memo[i][j]
	}
	return helper(sLen-1, tLen-1) 
};

4 ) 方案4: 动态规划

function numDistinct(s: string, t: string): number {
	const sLen = s.length, tLen = t.length, dp = new Array(sLen+1)
	for (let i = 0; i < sLen+1; i++) {
		dp[i] = new Array(tLen+1).fill(0)
	}
	for (let i = 0; i < sLen+1; i++) {
		for (let j = 0; j < tLen+1; j++) {
			if (j == 0) {		
				dp[i][j] = 1
			} else if (i == 0) { 
				dp[i][j] = 0
			} else {			
				if (s[i-1] == t[j-1]) {
					dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
				} else {
					dp[i][j] = dp[i-1][j]
				}
			}
		}
	}
	return dp[sLen][tLen]
}