题目描述

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.

Example 1:

Input:
  s = "barfoothefoobarman",
  words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.

Example 2:

Input:
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
Output: []

题意：给一个字符串s和一个字符串集合，集合中的字符串有相同的长度。找到所有s中的可行的子串使其成为字符串集合中所有单词的一种拼接。返回其所有的可行下标。

算法1

(暴力枚举)

暴力做法。枚举s中所有可能的起点，判断其是否满足要求，即使是暴力也有一些小技巧。首先用hash表存储词典中每个单词出现的个数，每个单词长度我们记为len。对于每个位置，我们同样使用一个hash表存储从这个位置开始的所有字符串及其出现次数，然后依次把它后面长度为len的字符串拿出来。如果这个字符串在hash表中没有出现过，那么返回false；否则判断当前字符串出现个数是否大于目标个数，如果大于，返回false，如果等于说明找到了一个新的可满足的字符串，更新satisfy，如果所有需要的字符串个数都满足了，就记录答案，返回。

时间复杂度分析：枚举所有起点$O(n)$，每次匹配至多匹配$m$个单词，那么时间复杂度为$O(n\*m\*len)$

C++ 代码

    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash;
        vector<int> res;
        int n = s.length(),m = words.size();
        if(n == 0 || m == 0) return res;
        int len = words[0].length(),end = n - m * len;
        if(n < m * len) return res;
        for(auto word:words)
            hash[word] ++;
        for(int i = 0 ;i <= end;i ++)
        {
            unordered_map<string,int> cur_hash;
            int satisfy = 0;
            for(int j = i;j <= n - len; j += len)
            {
                string cur = s.substr(j,len);
                if(hash.find(cur) == hash.end())
                    break;
                else 
                {
                    cur_hash[cur] ++;
                    if(cur_hash[cur] > hash[cur])
                        break;
                    else if(cur_hash[cur] == hash[cur])
                        satisfy ++;
                    if(satisfy == hash.size())
                    {
                        res.push_back(i);
                        break;
                    }
                }
            }
        }
        return res;
    }

算法2

(双指针) $O(n^2)$

题解2:双指针做法。因为每个单词中的长度len相同，那么我们可以根据每次枚举的起始位置将其划分为len组不同的匹配。

len = 3,s = abcdefghijkl
划分1: abc def ghi jkl
划分2: bcd efg hij
划分3: cde fgh ijk

那么问题其实就转换成了Leetcode76题，在S找一个最短的子串，包含T中所有的字母。只不过这一题中不能包含任何其他的字符，这就意味着我们当前读到的单词无法匹配就直接break。

首先枚举所有的划分起点位置，然后i,j分别代表当前窗口的左右指针，cur_hash记录当前窗口内每个单词出现的次数，satisfy记录已经满足的单词个数，每次读入一个单词：

• 如果当前单词没有出现过，说明失配了，那么将j指针后移，i指针转成j指针位置，重新匹配。
• 如果出现过，更新cur_hash：
• 如果当前单词出现个数等于我们需要的单词个数，那么说明找到了一个新的可满足的单词，更新satisfy。
• 如果当前单词单词出现个数大于我们需要的单词个数，那么需要将i指针后移，直至当前单词个数恰好等于需要的单词个数。i指针后移的过程中，需要更新cur_hash，同时如果删除的单词恰好从满足变成不满足也需要更新satisfy。
• 此时需要判断是否找到了一个可满足的序列，如果找到了记录答案，同时将i指针后移，同更新cur_hash和satisfy。

时间复杂度分析：枚举所有可能的划分$O(len)$，对于每一种划分，双指针最多匹配$O(n + m *len)$，所以总的指尖复杂度为$O((n + m * len) * len)$

C++ 代码

    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> hash;
        vector<int> res;
        int n = s.length(),m = words.size();
        if(n == 0 || m == 0) return res;
        int len = words[0].length(),end = n - m * len;
        if(n < m * len) return res;
        for(auto word:words)
            hash[word] ++;
        int size = hash.size();
        for(int k = 0;k < len ; k ++)
        {
            unordered_map<string,int> cur_hash;
            int satisfy = 0;
            for(int i = k,j = k;j <= n - len;)
            {
                string cur = s.substr(j,len);
                if(hash.find(cur) == hash.end())
                {
                    j = j + len;
                    i = j;
                    cur_hash.clear();
                    satisfy = 0;
                }else 
                {
                    cur_hash[cur] ++;
                    if(cur_hash[cur] == hash[cur])
                        satisfy ++;
                    else if(cur_hash[cur] > hash[cur])
                    {
                        while(i < j && cur_hash[cur] > hash[cur])
                        {
                            string temp = s.substr(i,len);
                            i += len;
                            cur_hash[temp] --;
                            if(cur_hash[temp] == hash[temp] - 1)
                                satisfy --;
                        }
                    }
                    if(satisfy == size)
                    {
                        string temp = s.substr(i,len);
                        cur_hash[temp] --;
                        satisfy --;
                        res.push_back(i);
                        i = i + len;
                    }
                    j = j + len;
                }
            }
        }
        return res;
    }