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

Difficulty: 困难

给定一个字符串 **s **和一些长度相同的单词 **words。**找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 **words **中单词串联的顺序。

示例 1：

输入：  s = "barfoothefoobarman",  words = ["foo","bar"]输出：[0,9]解释：从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。输出的顺序不重要, [9,0] 也是有效答案。

示例 2：

输入：  s = "wordgoodgoodgoodbestword",  words = ["word","good","best","word"]输出：[]

Solution

Language: ****

​

class Solution {
   public:    vector
   
     findSubstring(string s, vector
    
     & words) {
           if (s.size() <=0 || words.size() <=0) return {
   };        int n = words.size(),m = words[0].size();        if (m*n > s.size()) return {
   };        vector
     
      res;             unordered_map
      
       _map;        for (string a: words) _map[a]++;               for (int i=0;i<=s.size() - m*n;++i) {
               unordered_map
       
        window = _map;            int k = n,j = i;            while (k > 0 ) {
                   string str = s.substr(j, m);                if (!window[str]) break;                                 window[str]--;                k--,j+=m;            }            if (k==0) res.push_back(i);        }        return res;    }};
       
      
     
    
   

转载地址：http://vyyzi.baihongyu.com/