Fast C# solution using DP O(n^2)


  • 0
    L
    public int NumDistinct(string s, string t) {
        // Check the pre-conditions
        if (s == null || t == null)
        {
            return 0;
        }
        
        // We can use DP for this problem.
        // Given T := t.Length and S := s.Length()
        // We create a matrix dp[T, S]
        // In each cell [r,c] we store the possible subsequences
        // of s starting at r in s starting at c.
        var T = t.Length;
        var S = s.Length;
    
        // It is pointless to continue if the search string t is empty
        // or is bigger than s
        if (T == 0 || T > S)
        {
            return 0;
        }
    
        var dp = new int[T, S];
    
        // First initialize the last row
        var count = 0;
        int r, c;
        r = T - 1;
        for (c = S - 1; c >= 0; --c)
        {
            // If the current char in t is equal to the current char in s
            // we have a possible combination...
            // We update the count and store it into the cell
            if (t[r] == s[c])
            {
                ++count;
            }
    
            dp[r, c] = count;
        }
    
        // Now we update the rest of the matrix
        // We update only the lower triangle, the upper one does not make
        // sense to be updated since we have more characters left in t than what
        // we have in s, so there is no way we can find a subsequence
        var maxCol = S - 1;
        for (r = T - 2; r >= 0; --r)
        {
            --maxCol;
            count = 0;
            for (c = maxCol; c >= 0; --c)
            {
                // If the current char in t is equal to the current char in s
                // we have a possible combination...
                // We update the count and store it into the cell
                if (t[r] == s[c])
                {
                    // The count is update by the number of combination advancing t and s
                    count += dp[r + 1, c + 1];
                }
    
                dp[r, c] = count;
            }
        }
    
        return dp[0, 0];
    }

Log in to reply
 

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