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

分析

从s里面，找出由words里面的所有单词组成的字符子串（每个字符串仅出现一次），不要关注顺序。

该题和 3.Longest Substring Without Repeatition 类似，都是维护一个窗口去滑动，记左边界 left，右边界right

s长度 N

words里单个单词长度 M，words单词总数 L

那么对s遍历的右边界 last = N - M + 1

在 hashmap 中存入 words 中的每个单词，key是单词，value单词出现在words中的index。 O(L)

创建一个二维数组 table [2][L]

0行：记录words中每个单词出现的次数。 O(L)

1行：记录扫描时候，left和right之间窗口中，包含words的单词出现次数

创建一个一维数组 smapping，遍历s，记录每个单词是否在 workds中。如果存在，则放入在words中的index；如果不存在，则为-1。 O(N)

算法GIF解释：

代码

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

class  Solution { public :      vector< int > findSubstring(string s, vector<string>& words) {          int  N = s.size();          int  M = words[0].size();          int  L = words.size();          int  last = N - M + 1;          vector< int > result;          unordered_map<string,  int > mapping;          vector<vector< int >> table(2,vector< int > (L));            vector< int > smapping(last, -1);            int  index = 0, failures = 0;          for  ( int  i = 0; i < L; ++i) {              auto word = mapping.find(words[i]);              if  (word == mapping.end()) {                  failures++;                  mapping.insert({ words[i], index++ });                  word = mapping.find(words[i]);              }              table[0][word->second]++;          }            for  ( int  i = 0; i < last; ++i) {              auto word = mapping.find(s.substr(i, M));              if  (word != mapping.end()) {                  smapping[i] = word->second;              }              else  {                  smapping[i] = -1;              }          }            for  ( int  i = 0; i < M; ++i) {              int  currentFailures = failures;              fill(table[1].begin(), table[1].end(), 0);              int  L = i, R = i;              while  (R < last) {                  while  (currentFailures != 0 && R < last) {                      if  (smapping[R] != -1 && ++table[1][smapping[R]] == table[0][smapping[R]]) {                          currentFailures--;                      }                      R += M;                  }                    while  (currentFailures == 0 && L < R) {                      if  ((R - L) / M == words.size()) {                          result.push_back(L);                      }                      if  (smapping[L] != -1 && --table[1][smapping[L]] == table[0][smapping[L]] - 1) {                          currentFailures++;                      }                      L += M;                  }              }          }          return  result;      } };

 

附件列表