7-10 lines C++ Solutions with Detailed Explanations (O(m*n) time and O(m) space)


  • 51

    Well, a dynamic programming problem. Let's first define its state dp[i][j] to be the number of distinct subsequences of t[0..i - 1] in s[0..j - 1]. Then we have the following state equations:

    1. General case 1: dp[i][j] = dp[i][j - 1] if t[i - 1] != s[j - 1];
    2. General case 2: dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] if t[i - 1] == s[j - 1];
    3. Boundary case 1: dp[0][j] = 1 for all j;
    4. Boundary case 2: dp[i][0] = 0 for all positive i.

    Now let's give brief explanations to the four equations above.

    1. If t[i - 1] != s[j - 1], the distinct subsequences will not include s[j - 1] and thus all the number of distinct subsequences will simply be those in s[0..j - 2], which corresponds to dp[i][j - 1];
    2. If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with s[j - 1] and those without;
    3. An empty string will have exactly one subsequence in any string :-)
    4. Non-empty string will have no subsequences in an empty string.

    Putting these together, we will have the following simple codes (just like translation :-)):

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

    Notice that we keep the whole m*n matrix simply for dp[i - 1][j - 1]. So we can simply store that value in a single variable and further optimize the space complexity. The final code is as follows.

    class Solution {
    public:
        int numDistinct(string s, string t) {
            int m = t.length(), n = s.length();
            vector<int> cur(m + 1, 0);
            cur[0] = 1;
            for (int j = 1; j <= n; j++) { 
                int pre = 1;
                for (int i = 1; i <= m; i++) {
                    int temp = cur[i];
                    cur[i] = cur[i] + (t[i - 1] == s[j - 1] ? pre : 0);
                    pre = temp;
                }
            }
            return cur[m];
        }
    };

  • 0
    S

    Thanks so much for your detailed explanation on the boundary case. that's an important point in solving this problem.


  • 0
    L

    I can not understand the optimization, could you please explain as detailed as possible?


  • 4
    T

    Actually your code can be further improved on space by traversing index i backward. This way you dont need an extra variable to keep the last dp value. Here is my code:

    int numDistinct(string s, string t) {
         int n = s.length(), m = t.length();
         vector<int> dp(m+1, 0);
         dp[0] = 1;
         for (int j = 1; j <= n; j++){
             for (int i = m; i >= 1; i--){
                 dp[i] += s[j-1] == t[i-1] ? dp[i-1] : 0;
             }
         }
        return dp[m];
    }
    

  • 1
    W

    @jianchao.li.fighter said in 7-10 lines C++ Solutions with Detailed Explanations (O(m*n) time and O(m) space):

    If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with s[j - 1] and those without;

    I think in this sentence you may should mean "If t[i - 1] == s[j - 1], the number of distinct subsequences include two parts: those with t[i - 1] and those without;"


  • 0
    R

    Javascript version:

    var numDistinct = function(s, t) {
            var m = t.length, n = s.length;
            var cur = new Array(m+1);
            cur.fill(0)
            cur[0] = 1;
            for(var j = 1; j <= n; j++) {
                var pre = 1;
                for(var i = 1; i <= m; i++) {
                    var temp = cur[i];
                    cur[i] = cur[i] + (t[i-1] == s[j-1] ? pre : 0);
                    pre = temp;
                }
            }
            return cur[m];
    };
    

    Golang version:

    func numDistinct(s string, t string) int {
            m := len(t)
            n := len(s)
            cur := make([]int, m+1)
            for k,_ := range cur {
                cur[k] = 0
            }
            cur[0] = 1
            for j := 1; j <= n; j++ {
                pre := 1
                for i := 1; i <= m; i++ {
                    temp := cur[i]
                    a := 0
                    if t[i-1] == s[j-1] {
                        a = pre
                    }
                    cur[i] = cur[i] + a
                    pre = temp;
                }
            }
            return cur[m]
    }
    

  • 0
    L

    @tonygogogo Mind blown, can you explain the logic that allowed you to come up with the answer?


  • 0
    X

    @jianchao.li.fighter I do not agree with your boundary cases:

    • 1st, dp[0][j] represent number of distinct sequences from an empty string s equals any string with length j, then dp[0][j] = 0 for all j
    • 2nd, dp[i][0] represent number of distinct sequences from any string with length i equals an empty string t = "", and such distinct sequence exists and only can be an empty string "", so dp[i][0] = 1

    right ?


Log in to reply
 

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