本文共 1295 字，大约阅读时间需要 4 分钟。

题目

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).

解答

思路：定义两个map容器，结构都是

unordered_map
   
     counts;
   

key是字符串，value是该字符串出现的个数。

先对words进行遍历，初始化counts。 那下面就要遍历s了，但是我们没必要遍历到最后，因为要匹配整个words，所以下标只需到s_len-words_num*words1_len 这个很重要，许多超时的都是遍历到最后了。 之后用另一个unordered_map （seen）来计数

unordered_map
   
     seen;
   

假设某次遍历，开始下标是 i

对于words出现的每一个word，进行遍历，用j表示words中第j个word，并截取s中以i下标开始的字符串word，查看counts中是否包含这个字符串，如果包含，seen[word]就自增，否则（不包含），就是以i开始的字符串不满足，i++。 在上述过程中，seen[word]如果超过counts[word]，即出现的次数多了，肯定也不满足，直接跳转到i+1。 当所有的seen[word]都不超过counts[word]，这个表示seen中每个字符串的个数等于counts中字符串个数。把此时的下标i保存起来。

class Solution {public:    vector
   
     findSubstring(string s, vector
    
     & words) {    unordered_map
     
       counts;    for(int i=0;i