8s dp cpp solution


  • 0
    P
    class Solution {
    public:
        int numDistinct(string s, string t) {
            int ls=s.size(),lt=t.size();
            int dp[ls+1][lt+1];
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=ls;i++){
                if(s[i-1]==t[0]) dp[i][1]=dp[i-1][1]+1;
                else dp[i][1]=dp[i-1][1];
            }
            for(int i=1;i<=ls;i++){
                for(int j=2;j<=i&&j<=lt;j++){
                    dp[i][j] = dp[i-1][j];
                    if(s[i-1]==t[j-1]) dp[i][j] += dp[i-1][j-1];
                }
            }
            return dp[ls][lt];
        }
    };

  • 0
    W

    8 lines solution with c,and 0ms used

     int numDistinct(char* s, char* t) {
        int ls=strlen(s),lt=strlen(t);
        int dp[1000]={1};
        for(int i=1;i<=ls;i++)
            for(int j=lt;j>0;j--)
                if(s[i-1]==t[j-1])dp[j]+=dp[j-1];
        return dp[lt];
        }
    

Log in to reply
 

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