30. 串联所有单词的子串#

1
给定一个字符串 s 和一些 长度相同 的单词 words 。
2

3
找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
4

5
注意子串要与 words 中的单词完全匹配，
6

7
中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
8

9

10

11
示例 1：
12

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

20
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
21
输出：[]
22
示例 3：
23

24
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
25
输出：[6,9,12]
26

27

28
提示：
29

30
1 <= s.length <= 10^4
31
s 由小写英文字母组成
32
1 <= words.length <= 5000
33
1 <= words[i].length <= 30
34
words[i] 由小写英文字母组成

1
class Solution {
2
public:
3
    vector<int> findSubstring(string s, vector<string>& words) {
4
        vector<int> ans;
5
        int n = s.size();
6
        if(n <= 0 || words.empty()) return ans;
7
        int ws = words[0].size();    //words中的word的长度，为统一长度
8
        int ns = words.size();      //words中的word数量
9
        unordered_map<string, int> up; //保存words中的word
10
        for(auto & w : words)
11
        {
12
            up[w]++;  //记录每一个单词出现的次数
13
        }
14
        for(int i = 0; i < ws; i++)
15
        {
16
            int l = i, r = i; //从左开始
17
            int cnt = 0;  //下文ump存放的单词总数！
18
            unordered_map<string, int> ump;
19
            while(r + ws <= n)  //右边长度加每个单词长度要小于s的全长
20
            {
21
                string res = s.substr(r, ws); //在右边界加入一个单词
22
                r += ws;    //扩展右边界
23
                if(up.find(res) != up.end()) //查看res在up中的位置
24
                {
25
                    ump[res]++;
26
                    cnt++;
27
                    while(ump[res] > up[res])// 需要检查数量是否超过，超过则要右移left
28
                    {             //来缩小窗口
29
                        string tmp = s.substr(l, ws);
30
                        l += ws;
31
                        cnt--;
32
                        ump[tmp]--;
33
                    }
34
                    if(cnt == ns) ans.push_back(l);
35
                }
36
                else //未出现，舍弃此单词。清空
37
                {
38
                    l = r;
39
                    cnt = 0;
40
                    ump.clear();
41
                }
42
            }
43
        }
44
        return ans;
45
    }
46
};