LeetCode Problem:Distinct Subsequences

By | 2012 年 12 月 15 日

(2013-1-5更新了动态规划版本,见下面)
这题有点复杂,一开始拿到都不知道怎么下手。

尝试的路径是:
1·先试试看从T的size上简化看看。写一个例子S = aaaaa,T = a,很简单,数数就行。然后T=aa,发现没有太好的方法,怎么弄也算不出来最后结果。但是如果第一步查找记录下了所有的位置的话,只需要看该位置后面还有没出现T[1]就好了。比如S=aaba,T=ab,那么第一步查找得到{0,1,3},第二步只需要在这个集合内查看,S[0]后面有没有b,S[1]后面有没有b,S[3]后面有没有b。最后得到{02,12}两个结果。这样有了一个初步的算法,只不过非常消耗内存。小集合可以过,大集合内存超过限制。
2·内存如何超限的呢?比如当S=aaaa,T=aaa,的时候,第一轮结果{0,1,2,3},第二轮就变成了{01,02,03,12,13,23},可以看到,如果S再长一点的话,是很恐怖的。但是实际上从这里也能看出一点问题,就是02,12是可以合并的,因为下次它两个都会去查找S[2]之后有没有T[2],而且得到的结果是一样的。如果合并的话,不仅空间省了,时间也省了。所以就可以用一个int数组,记录在当前时刻(查找过程中T的下标),在S的某个位置结束的成功匹配个数。比如这个数组叫做matches,和S等大。那么第一轮下来matches[i] = (S[i] == T[0])。第二轮开始,针对每一个j = 1 … T.size() – 1,对matches中记录的每一个结束点去往后查找T[j],找到的话(比如在S[ii] == T[j]),那么新的matches[ii] += matches[i]。所以这里需要两个数组来回倒腾。最后写出代码220ms过了大集合测试。空间复杂度O(S.size()),时间复杂度O(S.size() * S.size() * T.size())。而且在查找的时候还可以简化,这样整体时间复杂度可以变成O(S.size() * T.size())



Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
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.



代码:220ms过大集合

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (T.size() == 0 || S.size() == 0 || S.size() < T.size())
            return 0;
        
        //at each position i in S, how many matches could be found with the substring end at S[i]
        int *matches = new int[S.size()];
        //temporary array for updating matches.
        int *mtemp = new int[S.size()];

        //1.initialize
        for(int i = 0; i < S.size(); ++i) {
            matches[i] = (S[i] == T[0] ? 1 : 0);
            mtemp[i] = 0;
        }
        
        for(int j = 1; j < T.size(); ++j) {
            const char tj = T[j];//process the char T[j]
            for(int ilast = 0; ilast < S.size(); ++ilast) {
                if (matches[ilast] == 0)//no possible matches
                    continue;
                for(int i = ilast + 1; i < S.size(); ++i) {
                    if(S[i] == tj) {
                        mtemp[i] += matches[ilast];//and the match count in ilast to new location
                    }
                }
            }
            for(int ilast = 0; ilast < S.size(); ++ilast) {
                matches[ilast] = 0;
            }
            int * t = matches;//switch matches and mtemp
            matches = mtemp;
            mtemp = t;
        }
        
        int sum = 0;
        for(int i = 0; i < S.size(); ++i) {
            sum += matches[i];
        }
        return sum;
    }
};



代码1:小集合可以过,大集合内存超过

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (T.size() == 0 || S.size() == 0)
            return 0;
        queue pls;//possible location start index in S
        
        //1.inite pls by searchin T[0] in S
        for(int i = 0; i < S.size(); ++i) {
            if (S[i] == T[0]) {
                pls.push(i);
            }
        }
        //2.one by one search T[j] in S, update the loast match index in pls or remove if no match fould
        const int levelEnd = -1;
        int j = 1;
        if(pls.size() && j < T.size()) pls.push(levelEnd);
        while(pls.size() && j < T.size()) {
            if(pls.size() > 1000) return 1000;
            char tj = T[j];
            int lasti = pls.front();
            pls.pop();
            if (lasti == levelEnd) {
                ++j;
                if (j == T.size()) 
                    break;
                if(pls.size()) pls.push(levelEnd);
            } else {
                for(int i = lasti + 1; i < S.size(); ++i) {
                    if(S[i] == tj) {
                        pls.push(i);
                    }
                }
            }
        }
        
        //3.finished
        return pls.size();
    }
};

<br>
Code rewrite at 2013-1-5
重写一次,用了动态规划搞定,时间复杂度是O(S.size() * T.size())

class Solution {
public:
    int numDistinct(string S, string T) {
        if(S.size() < T.size()) return 0;
        if(T.size() == 0) return 0;
        vector > ways (S.size(), vector(T.size(),0));
        //the first column
        ways[0][0] = (S[0] == T[0] ? 1 : 0);
        for(int is = 1; is < S.size(); ++is) {
            ways[is][0] = ways[is-1][0];
            if(T[0] == S[is]) {
                ways[is][0] += 1;
            }
        }
        //the remaining triangle
        for(int it = 1; it < T.size(); ++it) {
            //the item on the diagonal
            ways[it][it] = (S[it] == T[it] ? ways[it-1][it-1] : 0);
            //the items below
            for(int is = it + 1; is < S.size(); ++is) {
                ways[is][it] = ways[is-1][it];
                if(S[is] == T[it]) {
                    ways[is][it] += ways[is-1][it-1];
                }
            }
        }
        return ways[S.size()-1][T.size()-1];
    }
};



上面的代码用了O(S.size() * T.size())的空间,实际上没有必要,只需要2 * S.size()的空间就够了。

class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(S.size() < T.size()) return 0;
        if(T.size() == 0) return 0;
        int *ways = new int[S.size()];
        int *waysTemp = new int[S.size()];
        //the first charactor for T
        ways[0] = (S[0] == T[0] ? 1 : 0);
        for(int is = 1; is < S.size(); ++is) {
            ways[is] = ways[is-1];
            if(T[0] == S[is]) {
                ways[is] += 1;
            }
        }
        //the remaining charactors in T
        for(int it = 1; it < T.size(); ++it) {
            //the item on the diagonal
            waysTemp[it] = (S[it] == T[it] ? ways[it-1] : 0);
            //the items below
            for(int is = it + 1; is < S.size(); ++is) {
                waysTemp[is] = waysTemp[is-1];
                if(S[is] == T[it]) {
                    waysTemp[is] += ways[is-1];
                }
            }
            int *temp = ways;
            ways = waysTemp;
            waysTemp = temp;
        }
        int ret = ways[S.size()-1];
        delete ways;
        delete waysTemp;
        return ret;
    }
};



code rewrite at 2013-1-14, 36ms pass the large test

/*
Let ways(x,y) denote that from first x characters in S to first y characters in T needs ways(x,y) distinct ways.
then if we knew ways(i,j), i < n, i < m, then 
ways(n,m) = S[n-1] == T[m-1] ? ways(n-1,m-1) + ways(n-1,m) : ways(n-1,m)
ways(x,0) = x; x = 0,...,S.size()
ways(y,y) = S[y-1] == T[y-1] ? ways(y-1,y-1) : 0; y = 1,...,T.size()
*/
class Solution {
public:
    int numDistinct(string S, string T) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(S.size() < T.size()) return 0;
        int *ways = new int[S.size() + 1];
        int *waystemp = new int[S.size() + 1];
        for(int i = 0; i <= S.size(); ++i) {
            ways[i] = 1;
        }
        for(int lent = 1; lent <= T.size(); ++lent) {
            waystemp[lent] = (S[lent-1] == T[lent-1] ? ways[lent-1] : 0);
            for(int lens = lent + 1; lens <= S.size(); ++ lens) {
                waystemp[lens] = waystemp[lens - 1];
                waystemp[lens] += (S[lens-1] == T[lent-1] ? ways[lens-1] : 0);
            }
            int *temp = ways;
            ways = waystemp;
            waystemp = temp;
        }
        int ret = ways[S.size()];
        delete ways;
        delete waystemp;
        return ret;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注