My simple c++ dp solution in 10lines with O(n*m) in time and O(n) in space

  • 0

    Let dp[i][j] = {count(strs) | string set strs are substrings of s[0..j), and all string in strs equal to t[0..i)}

    we can find:

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

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

    To compress space, let cur[j] equal to dp[i][j] and pre[j] equal to dp[i-1][j].

    int numDistinct(string s, string t) {
        if(s=="") return (t=="")?1:0;
        int sl = s.length(), tl=t.length();
        vector< vector<int>> dp(2, vector<int> (sl+1, 1));
        for(int i=1; i<=tl; ++i){
            vector<int> &pre = dp[(i-1)%2];
            vector<int> &cur = dp[i%2];
            cur[0] = 0;  //t[0..i) is not empty but substring from s is empty
            for(int j=1; j<=sl; ++j)
                cur[j] = cur[j-1] + (s[j-1] == t[i-1]? pre[j-1]: 0);
        return dp[tl%2][sl];

Log in to reply

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