Hey Guys can you help me figure out https://leetcode.com/problems/distinct-subsequences/
Anonymous User
68
Career

https://leetcode.com/problems/distinct-subsequences/

CODE 1

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<int>> dp(s.size(),vector<int> (t.size(),INT_MIN));
        return helper(s,t,0,0,dp);
    }
private:
    int helper(string & s, string & t, int i,int k,vector<vector<int>>& dp){
        if(t.size()- k> s.size() - i) return 0;
        if(t[k]=='\0') return 1;
        if(dp[i][k]!=INT_MIN) return dp[i][k];
        int ans = 0;
        if(s[i]==t[k]){
            ans += helper(s,t,i+1,k+1,dp);
        }
        ans += helper(s,t,i+1,k,dp);
        return dp[i][k] = ans;
    }
};

CODE 2

class Solution {
public:
    int numDistinct(string s, string t) {
        vector<vector<int>> dp(s.size(),vector<int> (t.size()));
        return helper(s,t,0,0,dp);
    }
private:
    int helper(string & s, string & t, int i,int k,vector<vector<int>>& dp){
        if(t.size()- k> s.size() - i) return 0;
        if(t[k]=='\0') return 1;
        if(dp[i][k]!=0) return dp[i][k];
        int ans = 0;
        if(s[i]==t[k]){
            ans += helper(s,t,i+1,k+1,dp);
        }
        ans += helper(s,t,i+1,k,dp);
        return dp[i][k] = ans;
    }
};

To me both the codes look same but leetcode gives TLE for code 2 but accepts code 1 smoothly
Output of code 1
image

Output of code 2

image

please expain why this is happening

Comments (0)