3ms, 4-6 lines DP solution in C++, O(m*n) time complexity, O(n) space complexity


  • 1
    N

    Hi, all. Here is my solution using Dynamic Programming.

    Suppose the length of string s is m the length of string t is n. We can divide this problem into sub-problem of calculating a 2D array A[m][n+1], where A[i][j] represents the number of distinct subsequences of s's prefix at length i+1 that equals to t's prefix at length j.

    It's obvious that A[i][j] depends on A[i-1][j], and A[i-1][j-1] when t[j] equals to s[i]. The reason is the prefix of s at length i+1 should contain all subsequences of the prefix of s at length i. Moreover, when t[j-1] equals to s[i], we should also plus the number of subsequences of t's prefix at length j-1 in the s's prefix at length i-1. Thus, the recursion formula is:

    • A[i][j] = A[i-1][j] + A[i-1][j-1] if t[j-1] equals to s[i]

    Here is an example, s = "abcab", t = "ab", A is initialized as follows:

    A 0 1 2
    0 1 0 0
    1 1
    2 1
    3 1
    4 1

    Let's first calculating A[1][1]. Because t[0] = 'a' == s[0] = 'a', A[1][1] = A[0][1] + A[0][0] = 1. Then, we can calculate A[1][2], Because t[1] = 'b' ≠ s[0] = 'a', A[1][2] = A[0][2] = 0. We can fill in A in this way. The final result is shown as follows:

    A 0 1 2
    0 1 0 0
    1 1 1 0
    2 1 1 1
    3 1 2 1
    4 1 2 3

    Here, A[4][2] is the result we want. Three subsequences are shown in bold font as follows:

    • abcab
    • abcab
    • abcab

    Notice that A is calculated in a row-wise manner, we can use an 1D array at length n+1 instead of A. The code in C++ is shown as follows (3ms, O(m*n) time complexity, O(n) space complexity, 6 lines):

    class Solution {
    public:
        int numDistinct(string s, string t) {
            vector<int> match(t.size()+1);
            match[0] = 1;
            for (int i=0; i<s.size(); i++)
                for (int j=t.size(); j>0; j--)
                    match[j] += (t[j-1] == s[i] ? match[j-1] : 0);
            return match[t.size()];        
        }
    };
    

    You can also compress the code to 4 lines if you want :)

    class Solution {
    public:
        int numDistinct(string s, string t) {
            vector<int> match(t.size()+1);
            match[0] = 1;
            for (int i=0; i<s.size(); i++) for (int j=t.size(); j>0; j--) match[j] += (t[j-1] == s[i] ? match[j-1] : 0);
            return match[t.size()];        
        }
    };
    

Log in to reply
 

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