My C++ solution running 13ms, time complexity O(n^2), space complexity O(n)


  • 0
    P
    class Solution {
    public:
        int numDistinct(string S, string T) {
        	if(S.length() < T.length())
        		return 0;
        	vector<int> p0, p1, c0, c1;
        	int i, j, c, vi;
        	for(i = 0; i <= S.length() - T.length(); i++)
        	{
        		if(S[i] == T[0])
        		{
        			p1.push_back(i);
        			c1.push_back(1);
        		}
        	}
        	for(i = 1; i < T.length() && !p1.empty(); i++)
        	{
        		p0 = p1;
        		c0 = c1;
        		p1.clear();
        		c1.clear();    		
        		for(j = p0[0] + 1; j <= S.length() - T.length() + i; j++) 
        		{
        			if(S[j] == T[i])
        			{
        				p1.push_back(j);
        				c = 0; vi = 0;
        				while(vi < p0.size() && p0[vi] < j)
        				{
        					c += c0[vi];
        					vi++;
        				}
        				c1.push_back(c);
        			}
        		}
        	}
        	c = 0;
        	for(i = 0; i < c1.size(); i++)
        		c += c1[i];
        	return c;
        }
    };

Log in to reply
 

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