🌵115. Distinct Subsequences
https://leetcode.com/problems/distinct-subsequences/
js
/**
* @param {string} s
* @param {string} t
* @return {number}
*/
function numDistinct(s, t) {
const dp = []
for (let i = 0; i <= t.length; i++) {
dp[i] = new Array(s.length + 1).fill(i === 0 ? 1 : 0)
}
for (let i = 1; i <= t.length; i++) {
for (let j = 1; j <= s.length; j++) {
dp[i][j] = dp[i][j - 1] + (t[i - 1] === s[j - 1] ? dp[i - 1][j - 1] : 0)
}
}
return dp[t.length][s.length]
}py
class Solution(object):
def numDistinct(self, s, t):
"""
:type s: str
:type t: str
:rtype: int
"""
dp = [
[1 if i == 0 else 0 for j in range(len(s) + 1)]
for i in range(len(t) + 1)
]
for i in range(1, len(t) + 1):
for j in range(1, len(s) + 1):
dp[i][j] = dp[i][j - 1]
if t[i - 1] == s[j - 1]:
dp[i][j] += dp[i - 1][j - 1]
return dp[-1][-1]go
func numDistinct(s string, t string) int {
dp := [][]int{}
for i := 0; i <= len(t); i++ {
row := []int{}
for j := 0; j <= len(s); j++ {
if i == 0 {
row = append(row, 1)
} else {
row = append(row, 0)
}
}
dp = append(dp, row)
}
for i := 1; i <= len(t); i++ {
for j := 1; j <= len(s); j++ {
dp[i][j] = dp[i][j-1]
if t[i-1] == s[j-1] {
dp[i][j] += dp[i-1][j-1]
}
}
}
return dp[len(t)][len(s)]
}