Leetcode: Substring with Concatenation of All Words - c++编程基础

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:

S: "barfoothefoobarman"

L: ["foo", "bar"]

You should return the indices: [0,9].

(order does not matter).

一开始理解错题意了，以为只要有L中的单词在S中没有干扰词汇的连续出现就要记下来呢，提交发现不对，人家是each word in L exactly once.是要所有L中的词都出现一遍，中间不能有其他的干扰词汇。并且L中的词也会有重复。

错误代码：

vector findSubstring(string S, vector &L) {  
        // Note: The Solution object is instantiated only once.  
        set dic;  
        for(int i = 0; i < L.size(); i++)  
            dic.insert(L[i]);  
  
        vector res;  
        int wordlen = L[0].size();  
        set::iterator it;  
        int i = 0;  
        bool isLastOk = false;  
        while(i < S.size())  
        {  
            string sub = S.substr(i,wordlen);  
            it = dic.find(sub);  
            if(it != dic.end())  
            {  
                if(!isLastOk)  
                {  
                    res.push_back(i);  
                    isLastOk = true;  
                }  
                    i += wordlen;  
            }else  
            {  
                isLastOk = false;  
                i++;  
            }  
        }  
        return res;  
    }

正确代码如下：

vector findSubstring(string S, vector &L) {  
        // Note: The Solution object is instantiated only once.  
        map words;  
        map cur;  
        int wordNum = L.size();  
        for(int i = 0; i < wordNum; i++)  
            words[L[i]]++;  
        int wordLen = L[0].size();  
        vector res;  
        //if(S.size() < wordLen*wordNum)return res;  
        for(int i = 0; i <= (int)S.size()-wordLen*wordNum; i++)  
        {  
            cur.clear();  
            int j;  
            for(j = 0; j < wordNum; j++)  
            {  
                string word = S.substr(i+j*wordLen, wordLen);  
                if(words.find(word) == words.end())  
                    break;  
                cur[word]++;  
                if(cur[word]>words[word])  
                    break;  
            }  
            if(j == wordNum)  
                res.push_back(i);  
        }  
        return res;  
    }