题目描述:

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

For example, given:

s: “barfoothefoobarman”

words: [“foo”, “bar”]

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

(order does not matter).

首先使用暴力法, 将words中的词放入一个哈希表中, 这样可以在常数时间内找到它. 然后用一个双重循环来遍历字符串s.

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int wordsLen = words.size();
        if(wordsLen == 0)
            return ret;
        int wordLen = words[0].length(), sLen = s.length(), totalLen = wordsLen * wordLen;
        
        unordered_map<string, int> wordExistOrig;
        
        for(int i = 0; i < wordsLen; i++){
            if(wordExistOrig.count(words[i])){
                wordExistOrig[words[i]]++;
            }
            else{
                wordExistOrig[words[i]] = 1;
            }
        }
        
        for(int i = 0; i <= sLen - totalLen; i++){
            unordered_map<string, int> wordExist = wordExistOrig;
            bool valid = true;
            for(int j = i; j < totalLen + i; j += wordLen){
                string str = s.substr(j, wordLen);
                if(wordExist.count(str) == 0) {
                    valid = false;
                    break;
                }
                else{
                    wordExist[str]--;
                    if(wordExist[str] < 0){
                        valid = false;
                        break;
                    }
                }
            }
            if(valid) ret.push_back(i);
        }
        
        return ret;
    }
};

还可以使用一种"滑动窗口"方法, 或者是双指针方法, 思路参考这里: http://www.2cto.com/kf/201406/311648.html. 举例来说比如题目中的例子: "barfoothefoobarman"和数组["foo", "bar"], 首先窗口长度为0, 起始位置为0, 窗口长度和起始位置都是以单词长度的整数倍变化的, 这里是3, 首先把第一个单词放进窗口(用{}来表示窗口): {bar}foothefoobarman, 由于foo和bar每个都只出现一次, 所以把bar的剩余次数(这个次数保存在hash表中)减1变为0, 接下来把下一个单词放入窗口: {barfoo}thefoobarman, 同样把foo的次数减1变为0, 这时窗口中已经有两个单词, 与words数组的大小相同, 就可以把当前的窗口起始位置放入结果集中. 接下来是单词the, 这个单词在words数组中没有, 所以窗口可以直接跳过它, 将窗口起始位置越过的bar和foo的允许出现次数加1, 此时窗口位置位于barfoothe{}foobarman, 然后重复这个步骤. 为了不忽略类似abarfoo这种字符串中的结果, 所以要将窗口起始位置从0到单词长度3遍历一次.

代码如下, 运行时间36ms:

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        int wordsLen = words.size();
        if (wordsLen == 0)
            return ret;
        int wordLen = words[0].length(), sLen = s.length(), totalLen = wordsLen * wordLen;

        unordered_map<string, int> wordExist;

        for (int i = 0; i < wordsLen; i++) {
            if (wordExist.count(words[i])) {
                wordExist[words[i]]++;
            }
            else {
                wordExist[words[i]] = 1;
            }
        }
        for (int i = 0; i < wordLen; i++) {
            int slideLeft = i, j = i, wordFound = 0;

            while (slideLeft <= sLen - totalLen && j < sLen) {
                string str = s.substr(j, wordLen);
                if (wordExist.count(str) == 0) {
                    //下一个单词不再words中时将窗口初始位置移到当前之后的位置
                    j += wordLen;
                    for (; slideLeft < j; slideLeft += wordLen) {
                        string toDropStr = s.substr(slideLeft, wordLen);
                        if(wordExist.count(toDropStr))wordExist[toDropStr]++;
                    }
                    //slideLeft = j;
                    wordFound = 0;
                    continue;
                }
                if (wordFound == wordsLen) {
                    //当窗口满的时候丢弃最前端的字符串
                    string toDropStr = s.substr(slideLeft, wordLen);
                    wordExist[toDropStr]++;
                    slideLeft += wordLen;
                    wordFound--;
                }
                wordExist[str]--;
                if (wordExist[str] < 0) {
                    //当前字符串出现次数已满, 要不停的丢弃窗口最前端的字符串直到出现次数为0为止
                    while (wordExist[str] < 0) {
                        string toDropStr = s.substr(slideLeft, wordLen);
                        wordExist[toDropStr]++;
                        slideLeft += wordLen;
                        wordFound--;
                    }
                }
                wordFound++;
                if (wordFound == wordsLen) {//找到一个要求的位置
                    ret.push_back(slideLeft);
                }
                j += wordLen;
            }
            for (; slideLeft < j; slideLeft += wordLen) {
                //恢复每个单词出现的次数
                string toDropStr = s.substr(slideLeft, wordLen);
                if (wordExist.count(toDropStr)) wordExist[toDropStr]++;
            }
        }

        return ret;
    }
};