Got "Timeout" on this solution???


  • 0
    Y

    // The basic idea is that when we shrink window, we skip the letters which are not in T
    // My test is good.
    // Get timeout in leetcode
    class Solution
    {
    public:
    string minWindow(string S, string T) {
    string result;
    if(S.empty() || T.empty()){
    return result;
    }

    	if (S.length() < T.length())
    		return result;
    
    	unordered_map<char, int> map;
    	unordered_map<char, int> window;
    	for(int i = 0; i < T.length(); i++){
    		map[T[i]]++;
    }
    
    	queue < int, list < int > > search_queue;
    	int start = 0;
    	int end = 0;
    	int count = 0;
    	int min_len = S.length() + 1;
    	char token = 0;
    
    	while ( start <= S.length() - T.length() && map.find(S[start]) == map.end())
    	{
    		++start;
    	}
    
    	if ( start > S.length() - T.length() )
    		return result;
    
    	count = 1;
    	if ( count == T.length() )
    	{
    		result = S.substr(start, count);
    		return result;
    	}
    
    	search_queue.push(start);
    	
    	window[S[start]] = 1;
    	end = start + 1;
    
    	while ( end < S.length() )
    	{
    		if (map.find(S[end]) == map.end())
    		{
    			++end;
    			continue;
    		}
    
    		search_queue.push(end);
    
    		if (window.find(S[end]) == window.end())
    		{
    			window[S[end]] = 1;
    		}
    		else
    		{
    			window[S[end]] += 1;
    		}
    
    		if (window[S[end]] == map[S[end]])
    		{
    			++count;
    			
    			while (count == map.size())
    			{
    				int len = end - start + 1;
    				if (min_len > len)
    				{
    					min_len = len;
    					result = S.substr(start, len);
    				}
    
    				if (search_queue.empty())
    						return result;
    				start = search_queue.front();
    				search_queue.pop();
    
    				window[S[start]] -= 1;
    				if (window[S[start]] < map[S[start]])
    				{
    					--count;
    					if (search_queue.empty())
    						return result;
    				}
    				start = search_queue.front();
    			// while (count == T.length())
    			}
    		// if (window[S[end]] == map[S[end]])
    		}
    		++end;
    	}
    
    	return result;
    }
    

    };


  • 0
    Y

    Please ignore the question. I found a bug in it.


Log in to reply
 

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