LeetCode OJ-- Substring with Concatenation of All Words ***

https://oj.leetcode.com/problems/substring-with-concatenation-of-all-words/

找S中子串，每个元素都在T中出现了，且所有T中元素都在S子串中出现了

class Solution {
public:
    vector<int> findSubstring(string S, vector<string> &L) {
        vector<int> ans;
        if(S.empty() || S.size() == 0 || L.empty() || L.size() == 0)
            return ans;
        
        // L is longer
        int len = L.size() * L[0].size(); 
        if(len > S.size())
            return ans;
        
        unordered_map<string,int> dictL;
        for(int i = 0; i< L.size(); i++)
            dictL[L[i]] += 1;
        
        unordered_map<string,int> _dict;
        for(int i = 0; i + len <= S.size(); i++)
        {
            string subS = S.substr(i,len);

            _dict.clear();
            bool flag = true;
            
            for(int j = 0; j < len; j+= L[0].size())
            {
                string subLittle = subS.substr(j,L[0].size());
                if(dictL.find(subLittle) == dictL.end()) //不属于目标里面的
                {
                    flag = false;
                    break;
                }

                _dict[subLittle] += 1;
                if(_dict[subLittle] > dictL[subLittle])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                ans.push_back(i);
            
        }
        return ans;
    }
};

超时、超时、超时、超时……

教训就是，有时候超时不是算法的问题，而是实现的不好。具体看下一篇博客