[Microsoft][LeetCode] 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:

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

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

Approach: We are going to use DP here. We are going to maintain a 2D table where Table[i][j] will tell the number of subsequences of s[0...j] of t[0...i]. Obviously Table[Length(t)][Length(s)] will be our answer. Here is how we will fill the table:

• We take the 2D Table of size Table[Length(t) + 1][Length(s + 1]
• For all i = 0...Length(s): Table[0][i] = 1 as if t is empty that means for s[0...i] will have exactly 1 number os subsequence which is equal to t.
• Table[i][j] = 
• Table[i][j - 1] if t[i - 1] != s[j - 1] 
• Table[i - 1][j - 1] + Table[i][j - 1] otherwise.

That's all!

 

Implementation in C#:

    public int NumDistinct(string s, string t) 

    {

        int[,] table = new int[t.Length + 1, s.Length + 1];

        for (int i = 0; i <= s.Length; ++i)

        {

            table[0, i] = 1;

        }

        for (int i = 1; i <= t.Length; ++i)

        {

            for (int j = 1; j <= s.Length; ++j)

            {

                if (t[i - 1] == s[j - 1])

                {

                    table[i, j] = table[i - 1, j - 1] + table[i, j - 1];

                }

                else

                {

                    table[i, j] = table[i, j - 1];

                }

            }

        }

        return table[t.Length, s.Length];

    }

Complexity: O(m * n)