LeetCode30-与所有单词相关联的字符串

题目：给定一个字符串s和一些长度相同的单词words。在s中找出可以恰好串联words中所有单词的子串的起始位置。
思路一：从字符串s的0位起，遍历以i为起始字符位置、word长度的字符串。如果子串连续命中words.size()次，则将i放入结果列表中。
评价：这种暴力模式，beats约6%。

代码如下：

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> result;
        if(s.empty() || words.empty()) return result;
        int sLen=s.size();
        int wordLen=words[0].size();
        int wordsLen=words.size()*wordLen;
        int pos=0;
        while(pos<=sLen-wordsLen){
            int temPos=pos;
            vector<bool> mark(words.size(),true);
            int i=0;
            for(;i<words.size();i++){
                string curWord=s.substr(temPos,wordLen);
                int wordPos=findWord(words,curWord,mark);
                if(wordPos==words.size()){
                    pos++;
                    break;
                }
                mark[wordPos]=false;
                temPos+=wordLen;                    
            }
            if(i==words.size()){
                result.push_back(pos);
                pos++;
            }
        }
        return result;
    }
private:
    int findWord(vector<string> &words,string word,vector<bool>& mark){
        int i=0;
        while(i<words.size()){
            if(words[i]==word  && mark[i])
                return i;
            i++;
        }
        return i;
    }
};

思路二：
每个字符串有三种可能：
1.是words中的字符串元素，对应的map中可用个数>0
2.是words中的字符串元素，对应的map中的可用个数=0
3.不是words中的字符串元素

代码如下：

    class Solution {
    public:
        vector<int> findSubstring(string s, vector<string>& words) {
            vector<int> result;
            if (s.empty() || words.empty()) return result;
            int sLen = s.size();
            int wordLen = words[0].size();
            int wordsLen = words.size()*wordLen;
            map<string, int> wordsMap;
            initialWords(words, wordsMap);
            for (int beginPos = 0; beginPos<wordLen; beginPos++){
            int pos = beginPos;
            deque<string> targetWord;
            map<string, int> copyMap(wordsMap);
            while (pos <= (sLen - wordsLen + wordLen * targetWord.size())){
                string curWord = s.substr(pos, wordLen);
                if (copyMap.find(curWord) != copyMap.end()){
                    if (copyMap[curWord]>0){
                        copyMap[curWord]--;
                        targetWord.push_back(curWord);
                    }
                    else{
                        //reInitaial(copyMap,wordsMap);
                        string dequeWord = *(targetWord.begin());
                        while (dequeWord != curWord){
                            targetWord.pop_front();
                            copyMap[dequeWord]++;
                            dequeWord = *(targetWord.begin());
                        }
                        targetWord.pop_front();
                        targetWord.push_back(curWord);
                    }
                    if (targetWord.size() == words.size())
                        result.push_back(pos - wordsLen + wordLen);
                }
                else{
                    reInitial(copyMap, wordsMap);
                    targetWord.clear();
                }
                pos += wordLen;
            }
        }
        return result;
    }
private:
    void reInitial(map<string, int> &copyMap, map<string, int> &wordsMap){
        for (auto iter1 = copyMap.begin(), iter2 = wordsMap.begin(); iter1 != copyMap.end(); iter1++, iter2++)
            iter1->second = iter2->second;
    }
    void initialWords(vector<string> &words, map<string, int> & wordsMap){
        for (auto iter = words.begin(); iter != words.end(); iter++){
            wordsMap[*iter]++;
        }
    }
};