LeetCode 30 Substring with Concatenation of All Words-蒲公英云

LeetCode 30 Substring with Concatenation of All Words

红太狼 2021-12-03 04:57 244阅读 0赞

题目

食之无味的题目

class Solution {
public:
    map<string,int> m;
    map<int,string> m2;
    map<string,int> m3;
    int b[100005];
    int c[100005];
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if(words.size()==0)
            return ans;
        if(s.length()==0)
            return ans;
         for(int i=0;i<words.size();i++)
         {
             m[words[i]]++;
         }
        int len = words[0].length();
        int index=0;
         for(int i=0;i<s.length();i++)
         {
             string a="";
             for(int k=i;k<i+len && k<s.length();k++)
             {
                 a+=s[k];
             }
             if(m[a]!=0)
             {
                 b[i]=m[a];
                 m2[i]=a;
                 c[index++]=i;
             }
         }
         for(int i=0;i<index;i++)
         {
             m3.clear();
             m3[m2[c[i]]]++;
             int j=i;
             int k=i+1;
             int x=1;
             int tag=1;
             if(s.length()-c[i] < len * words.size())
                 break;
             while(j<index&&k<index)
             {
                 if(c[k]-c[j]<len)
                 {
                    k++;
                    continue;
                 }
                 else if(c[k]-c[j]==len)
                 {
                     int y=++m3[m2[c[k]]];
                     if(y>m[m2[c[k]]])
                     {
                         tag=0;
                         break;
                     }
                     else
                     {
                         x++;
                         j=k;
                         k++;
                         if(x==words.size())
                         {
                             tag=1;
                             break;
                         }
                     }
                 }
                 else{
                     break;
                 }
             }
             if(x<words.size())
             {
                 tag=0;
             }
             if(tag==1)
                 ans.push_back(c[i]); 
         }
        return ans;
    }
};