Leetcode 115 Solution

This article provides solution to leetcode question 115 (distinct-subsequences).
Categories:
Tags:
Access this page by simply typing in "lcs 115" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution {
public:
    int numDistinct(string s, string t) {
        int m = s.size();
        int n = t.size();
        int dp[m][n];
        
        if (t.size() == 0)
            return 1;
        if (s.size() == 0)
            return 0;
        
        dp[0][0] = s[0] == t[0];
        
        for (int j = 1; j < t.size(); j++)
            dp[0][j] = 0;
        
        for (int i = 1; i < s.size(); i++)
            dp[i][0] = dp[i - 1][0] + (s[i] == t[0]);
        
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                
                if (s[i] == t[j])
                    dp[i][j] += dp[i - 1][j - 1];
            }
        }
        
        return dp[s.size() - 1][t.size() - 1];
    }
};