My c++ DP solution with O(m*n) time as well as space complexity


  • 0
    H

    When constructing the dp table, dp[j][i] means we take the first j characters in S and the first i characters in T into consideration. Then the logic is:

    1. the jth of S and ith of T are the same: dp[j][i] should equal to dp[j-1][i-1]+dp[j-1][i]. Where dp[j-1][i-1] means the number of combinations that if we force the ith of T to locate on the jth of S. And dp[j-1][i] means the number of combinations that if we force the ith of T NOT to locate on the jth of S.

    2. the jth of S and ith of T are different: dp[j][i] should equal to only dp[j-1][i], which is the number of combinations that we force the ith of T NOT to locate on the jth of S.

    And the code also deals with the initial values of the dp table.

        class Solution {
     public:
    
    	 int numDistinct(string S, string T) {
    		 vector<vector<int>> dp(S.length() + 1, vector<int>(T.length() + 1, 0));
             for (int i = 0; i <= S.length(); ++i) dp[i][0] = 1;
             
    		 for (int i = 1; i <= T.length(); ++i) { // i is for T
    			 for (int j = i; j <= S.length(); ++j) { // j is for S
    				 if (S[j - 1] == T[i - 1]) {
    					 dp[j][i] = dp[j - 1][i - 1] + dp[j - 1][i];
    				 }
    				 else {
    					 dp[j][i] = dp[j-1][i];
    				 }
    			 }
    		 }
    
    		 return dp[S.length()][T.length()];
    	 }
     };

Log in to reply
 

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