LeetCode30. 串联所有单词的子串

题目描述

本题目来自LeetCode上的『30. 串联所有单词的子串』

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

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

示例1：

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

提示

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

题解

题目要求用上 words 中所有单词，设每个单词长 len，words 长度 n，s 长度 m，窗口最大为 windowLen = len * n。首先使用哈希表 mp 统计 words 中每个单词出现的次，设窗口 [i,j] 的起点为 start，i, j 移动的步长为 len。扩张右边界 j， 设当前遍历的字串为 temp = s.substr(j, len) 有以下几种情况：

1. temp 不在 mp 中，那么包含 temp 的字串都不符合要求，直接从 temp 之后的字符开始遍历。
2. temp 在窗口中出现的次数大于 words 中的次数，则需要移动左边界 i，直到出现次数相等。
3. 若窗口大小等于 windowLen，则是一个答案。

窗口起点 start 只需要在 [0,len) 的范围内就可以保证遍历到所有的情况。

代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string,int> mp;
        int len = words[0].size();
        int m = s.size(), n = words.size();
        int windowLen = len * n;
        vector<int> ans;
        if (m < windowLen) return ans;
        for (const auto& word: words) ++mp[word];
        
        for (int start = 0; start < len; ++start) {
            int i = start, j = start;
            unordered_map<string,int> cnts;
            while (i < m - windowLen + 1) {
                bool flag = false;
                while (j < i + windowLen) {
                    string temp = s.substr(j, len);
                    j += len;
                    // 情况1：temp 不在 mp 中
                    if (mp.find(temp) == mp.end()) {
                        flag = true;
                        i = j;
                        cnts.clear();   // 窗口中的子串都不符合要求
                        break;
                    }
                    // 情况2：temp 在窗口中出现的次数大于`words 中的次数
                    if (++cnts[temp] > mp[temp]) flag = true;
                    while (cnts[temp] > mp[temp]) {
                        --cnts[s.substr(i, len)];
                        i += len;
                    }
                    if (flag) break;
                } 
                // 情况3：符合条件
                if (!flag) {
                    ans.emplace_back(i);
                    --cnts[s.substr(i, len)];
                    i += len;
                }
            }
        }

        return ans;
    }
};

复杂度分析

$n$ 为 $words$ 长度，$m$ 为 $s$ 长度，$len$ 为每个单词长度。

• 时间复杂度：$O(n+len\times m)$
• 空间复杂度：$O(n\times len)$