0115. Distinct Subsequences

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

Description

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.
**rabb**b**it**
**ra**b**bbit**
**rab**b**bit**

Example 2:

**Input:** s = "babgbag", t = "bag"
**Output:** 5
**Explanation:**
As shown below, there are 5 ways you can generate "bag" from S.
**ba**b**g**bag
**ba**bgba**g**
**b**abgb**ag**
ba**b**gb**ag**
babg**bag**

Constraints:

• 1 <= s.length, t.length <= 1000

• s and t consist of English letters.

ac

class Solution {
    public int numDistinct(String s, String t) {
        // edge cases
        if (s == null || t == null || s.length() < t.length()) return 0;

        int slen = s.length(), tlen = t.length();
        int[][] dp = new int[tlen+1][slen+1];

        // init
        for (int si = 0; si <= slen; si++) {
            dp[0][si] = 1;
        }

        for (int ti = 1; ti < dp.length; ti++) {
            for (int si = 1; si < dp[0].length; si++) {
                if (s.charAt(si-1) == t.charAt(ti-1)) {
                    dp[ti][si] = dp[ti][si-1] + dp[ti-1][si-1];
                } else {
                    dp[ti][si] = dp[ti][si-1];
                }
            }
        }

        return dp[tlen][slen];
    }
}

/*
dp[ti][si], s.substring(0, si) contains #distinct subsequences of t.substring(0, ti)

*/