Share my optimized O(n^2) code


  • 0
    O
    class Solution {
    public:
        int numDistinct(string s, string t) {
            if (t.size() > s.size() || t.size() == 0)
                return 0;
            
            int m = s.size();
            int n = t.size();
            int dp[m + 1][n + 1];
            for (int i = 0; i <= m; i++)
                dp[i][0] = 1;
            
            for (int j = 1; j <= n; j++) {
                for (int i = j; i <= m; i++) {
                    if (i == j)
                        if (s[i - 1] == t[j - 1])
                            dp[i][j] = dp[i - 1][j - 1];
                        else /* s[i - 1] != t[j - 1]*/
                            dp[i][j] = 0;
                    else /* i > j*/
                        if (s[i - 1] == t[j - 1])
                            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                        else /* s[i - 1] != t[j - 1]*/
                            dp[i][j] = dp[i - 1][j];
                }
            }
            
            return dp[m][n];
        }
    };

Log in to reply
 

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