LeetCode()Substring with Concatenation of All Words 为什么我的超时呢?找不到原因了!!!

超时代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        map<string,int> coll;
        for(auto i:words)
            coll[i]++;
        vector<int> res;
        int len=words[0].size(),sum=words.size();
        for(int k=0;k<=s.length()-len*sum;k++)
            if(check(s,k,len,sum,coll))
                res.push_back(k);
        return res;
    }
    bool check(string s,int start,int len,int sum,map<string,int> coll)
    {
        for(int i=start;i<=s.length()-len && sum!=0;i+=len)
        {
            string str=s.substr(i,len);
            auto d=coll.find(str);
            if(coll[str]>0 && d != coll.end())
            {
                coll[str]--;
                sum--;
            }
            else
                return false;
        }
        if(sum==0)
            return true;
        else
            return false;
    }
};

  这个和我的没有什么区别吧?为什么就可以呢?

class Solution {
private:
    int wordLen;
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        unordered_map<string, int>wordTimes;
        for(int i = 0; i < L.size(); i++)
            wordTimes[L[i]]++;
        wordLen = L[0].size();
         
        vector<int> res;
        for(int i = 0; i <= (int)(S.size()-L.size()*wordLen); i++)
            if(helper(S, i, wordTimes, L.size()))
                res.push_back(i);
        return res;
    }
     
    //判断子串s[index...]的前段是否能由L中的单词组合而成
    bool helper(const string &s, int index, 
        unordered_map<string, int>wordTimes, int wordNum)
    {
        for(int i = index; wordNum != 0 && i <= (int)s.size()-wordLen; i+=wordLen)
        {
            string word = s.substr(i, wordLen);
            auto ite = wordTimes.find(word);
            if(ite != wordTimes.end() && ite->second > 0)
                {ite->second--; wordNum--;}
            else return false;
        }
        if(wordNum == 0)return true;
        else return false;
    }
};

  

原文地址:https://www.cnblogs.com/yanqi110/p/4993247.html