LeetCode 30 Substring with Concatenation of All Words

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

[题目][Link 1]

食之无味的题目

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;
            
        }
        
       
    };

转载于:https://www.cnblogs.com/dacc123/p/11196898.html

[Link 1]: https://leetcode.com/problems/substring-with-concatenation-of-all-words/