My solution got TLE, any suggestions for improvement?


  • 0
    L
    class Solution {
    public:
    
      bool isContain(const string& str, unordered_map<string, int> wordMap, const int& wordLength)
        {
            for (unsigned i = 0; i < str.length(); i += wordLength)
            	if (wordMap[str.substr(i, wordLength)] == 0)
            		return false;
            	else
            		-- wordMap[str.substr(i, wordLength)];
            return true;
        }
    
        vector<int> findSubstring(string S, vector<string> &L)
        {
        	int wordLength = L[0].size();
        	unsigned totalLength = wordLength * L.size();
        	vector<int> result;
        	if (S.length() < totalLength)
        		return result;
        	unordered_map<string, int> wordMap;
        	for (unsigned i = 0; i < L.size(); ++i)
        		++ wordMap[L[i]];
        	for (unsigned i = 0; i < S.length() - totalLength + 1; ++i)
        		if (isContain(S.substr(i, totalLength), wordMap, wordLength))
        			result.push_back(i);
        	return result;
        }
    };

Log in to reply
 

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