Easy to grasp C++ Solution


  • 0
    F
    class Solution {
    public:
        int numDistinct(string s, string t) {
            /** dp[i][j] means t[0..j-1] appears in s[0...i-1] for ** times. 
             *  if s[i-1]==t[j-1]   
             *     dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
             *  else
             *     dp[i][j] = dp[i-1][j]
             **/
            int ss = s.size(), tt = t.size();
            vector<vector<int>> dp(2, vector<int>(tt + 1, 0));
            for (int i = 0; i <= ss; i++) {
                for (int j = 0; j <= tt; j++) {
                    if (i == 0 && j == 0) dp[i&1][j] = 1;
                    else if (i == 0) dp[i&1][j] = 0;
                    else if (j == 0) dp[i&1][j] = 1;
                    else dp[i&1][j] = dp[(i-1)&1][j] + (s[i-1] == t[j-1] ? dp[(i-1)&1][j-1] : 0);
                }
            }
            return dp[ss&1][tt];
        }
    };

Log in to reply
 

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