c++ solution with comment in code, beats 97% cpp submission


  • 0
    Y

    Just in case you need it....
    The complexity should be O(n).
    The main idea is
    define a slide window, whose start and end index is 'is' and 'ie'.
    Once got a new word in front of 'ie',
    ---- if no conflict, add it into the window by ie+=wordLen, and check if the window has all words.
    ---- if conflicted, move 'is' forward by is += wordLen, until the conflict is removed.
    If no word is matched in front of 'ie', the slide window will shrink to 0, and is=ie=ie+wordLen.

    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            int wordLen=words[0].length();
            int TotalLen=wordLen*words.size();
            vector<int> result;
            if(wordLen>s.length())return result;
            //----------------------------------------------------
            //assign index to every word, and get the count of every word.
            unordered_map<string,int>wordDic;
            vector<int> wordCount;
            int wordIndex=0;
            for(int i=0;i<words.size();++i)
            {
                if(wordDic.count(words[i])==0)
                {
                    wordDic.emplace(words[i],wordIndex++);
                    wordCount.push_back(1);
                }
                else
                    wordCount[wordDic[words[i]]]+=1;
            }
            //----------------------------------------------------
            // Search all the words in s, and save indices in vector Founds
            // if s="barfoothefoobarman", and words=["foo","bar"]
            // then Found =[1,-1,-1,0,-1,-1,-1,-1,-1,0,-1,-1,1,-1,-1,-1]
            vector<int> Founds;
            int ss=s.length()-wordLen;
            for(int i=0;i<=ss;++i)
            {
                string str=s.substr(i,wordLen);
                if(wordDic.count(str)>0)
                    Founds.push_back(wordDic[str]);
                else Founds.push_back(-1);
            }
            //----------------------------------------------------
            //Search all words combination based on Founds, and wordCount.
            bool Ini=true;
            for(int x=0;x<wordLen;++x)
            {
                //'is' and 'ie' are start and end of a slide window.
                //Once got a new word in front of 'ie', 
                //   if no conflict, add it into the window by ie+=wordLen, and check if the window has all words.
                //   if conflicted, move 'is' forward by is+=wordLen, until the conflict is removed.
                //If no word is matched in front of 'ie', the slide window will shrink to 0, and is=ie=ie+wordLen;
                int is=x,ie=x;
                vector<int>MissedWord(wordCount);   //All the words which need to be found
                int MissedWordCount=words.size();   //The total count of words which need to be found.
                while(true)
                {
                    if(ie>=Founds.size())break;
                    //If no word is matched in front of 'ie', the slide window will shrink to 0, and is=ie=ie+wordLen;
                    //All found words will be cleared.
                    if(Founds[ie]<0)    
                    {
                        is=ie+wordLen;
                        ie=ie+wordLen;
                        if(!Ini)    //clear all found word.
                        {
                            MissedWord=vector<int>(wordCount);
                            MissedWordCount=words.size();
                            Ini=true;
                        }
                        continue;
                    }
                    Ini=false;
                    //A word is matched in front of ie
                    if(MissedWord[Founds[ie]]>0)    //no confliction    
                    {
                        MissedWord[Founds[ie]]-=1;
                        MissedWordCount-=1;
                        ie+=wordLen;
                        if(MissedWordCount==0)result.push_back(ie-TotalLen);
                        continue;
                    }
                    else    //has confliction, try to remove the confliction by moving 'is' forward.
                    {
                        while(MissedWord[Founds[ie]]==0)
                        {
                            MissedWord[Founds[is]]+=1;
                            MissedWordCount+=1;
                            is+=wordLen;
                        }
                        continue;
                    }
                }
            }
            return result;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.