Share my C++ 20ms dp solution


  • 0
    Z

    dp[i][j] indicates numDistinct(s[0~(i-1)], t[0~(j-1)])

    class Solution {
    public:
    	int numDistinct(string s, string t) {
    		int lens = s.length();
    		int lent = t.length();
    		
    		if (lens < lent) return 0;
    		vector<vector<int>> dp(lens+1, vector<int>(lent+1, 0));
    		for (int i=0; i<=lens; i++)
    			dp[i][0] = 1;
    		for (int i=1; i<=lens; i++)
    		for (int j=1; j<=lent; j++) {
    			if (s[i-1] == t[j-1]) dp[i][j] += dp[i-1][j-1];
    			dp[i][j] += dp[i-1][j];
    		}
    		
    		return dp[lens][lent];
    	}
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.