115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

JavaScript

/**
 * @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]
}

Python

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)]
}