115. Distinct Subsequences

题目

Given a string S and a string T, count the number of distinct subsequences of S which equals T.A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).Here is an example:S = "rabbbit", T = "rabbit"Return 3.

解析

• 此题花费很多时间，对递推公式理解不清楚，用一维表示减少空间
• 对比最大公共子序列和子串

//115. Distinct Subsequencesclass Solution_115 {public:    int numDistinct(string S, string T) { //母串和子串匹配的次数        int lenx = T.size(); //子串        int leny = S.size(); //母串        if (lenx==0||leny==0)        {            return 0;        }        vector
    
     
       > dp(leny + 1, vector
      
       (lenx + 1, 0));        for (int i = 0; i <= leny;i++) //遍历母串        {            for (int j = 0; j <= lenx;j++) //遍历子串            {                if (j==0)                {                    dp[i][j] = 1; //当子串长度为0时，所有次数都是1                    continue;                }                if (i>=1&&j>=1)                {                    if (S[i - 1] == T[j - 1]) //当前母串和子串当前元素相等                    {                        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];                    }                    else                    {                        dp[i][j] = dp[i-1][j];                    }                }                            }        }        return dp[leny][lenx];    }    int numDistinct2(string s, string t) {        vector
       
         match(t.size() + 1);        match[0] = 1;        for (int i = 0; i
        
         0; j--)            match[j] += (t[j - 1] == s[i] ? match[j - 1] : 0);        return match[t.size()];    }    int numDistinct1(string S, string T) {  //bug.计算最长公共子序列    //测试用例:    //  "ddd", "dd"    //  对应输出应该为:3    //  你的输出为 : 2        int lenx = S.size();        int leny = T.size();        if (lenx==0||leny==0)        {            return 0;        }        vector
         
          
           > vecs(leny+1, vector
           
            (lenx+1, 0)); for (int i = 1; i <= T.size();i++) //行 { for (int j = 1; j <=lenx;j++) //列 { if (S[j-1]==T[i-1]) { vecs[i][j] = vecs[i-1][j - 1] + 1; } else { vecs[i][j] = max(vecs[i - 1][j], vecs[i][j - 1]); } } } int cnt = 0; if (vecs[leny][lenx] > 0){ cnt++; for (int i = lenx - 1; i > 0; i--) { if (vecs[leny][i] == vecs[leny][lenx]) { cnt++; } } } return cnt; }};
           
          
         
        
       
      
     
    

题目来源