LeetCode-30.串联所有单词的子串_串联所有单词的子串c

地址：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

思路：用无序map保留words,遍历字符串s，同时按照words中单词的长度分段处理字符串s,这样可以不必每次清空map

Code:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        unordered_map<string,int> imap,pi;
        int n=words.size(),m=0;
        if(n)    m=words[0].size();
        if(!s.size()||!m)  return res;
        for(int i=0;i<n;++i)
            ++imap[words[i]];
        string str;
        bool boo;
        for(int k=0;k<m;++k)
        {
            pi.clear(); boo=true;
            for(int j=0;j<n;++j)
            {
                str.assign(s,k+j*m,m);
                ++pi[str];
            }
            for(auto c:imap)
                if(pi[c.first]!=c.second){
                    boo=false;  break;
                }
            if(boo){
                res.push_back(k);
            }
            for(int i=k,j=k+n*m;j<=(int)s.size()-m;i+=m,j+=m)
            {
                str.assign(s,i,m);
                --pi[str];
                str.assign(s,j,m);
                ++pi[str];
                boo=true;
                for(auto c:imap)
                    if(pi[c.first]!=c.second){
                        boo=false;  break;
                    }
                if(boo){
                    res.push_back(i+m);
                }
            }
        }
        return res;
    }
};