算法题007：串联所有单词的子串

发表于 分类于 本文字数： 1.9k 阅读时长 ≈ 7 分钟

题目

题目来源：30. 串联所有单词的子串

题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

1
2
3
4
5
6
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

1
2
3
4
5
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

1
2
3
4
5
6
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示：

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

思路

为了方便起见，记 words.length 为 n，words[i].length 为 n2。

一个暴力的解法是，依次遍历 s 的每一个下标 i，然后判断以下标 i 为起始的长度为 n * n2 的子串（s[i : i + n * n2)）是否是一个串联子串。该解法类似于暴力求解字符串匹配问题。显然，对于这道困难题，这种做法的时间复杂度是不合格的。

因此，我们要想办法优化该做法。注意到题目中的“words 中所有字符串长度相同”。这显然是一个非常特殊的条件。假设我们已经考察了 s1 = s[i : i + n * n2)，并且记录了该子串与串联子串相差多少个 word，记该状态为 state1。那么，当我们考察 s2 = s[i + n2 : i + n * (n2 + 1)) 时，s2 比 s1 少一个子串 s[i : i + n2)，多一个子串 s[i + n * n2: i + n * (n2 + 1))，且这两个子串的长度都与 word 的长度相同。那么，我们就很容易根据 state1 以及这两个引起变化的子串求出 s2 距离达成串联子串相差多少个 word，即求出状态 state2。

让我们举个例子，假设 words = ["ab","cd","ef"]，s = "ggcdabef"。则此时 n = 3，n2 = 2。

令 s1 = s[0: 6) = "ggcdab"，此时 s1 距离达成串联子串的条件多出一个 word gg，少了一个 word ef —— 该状态为 state1。当我们考察 s2 = s[0 + 2, 6 + 2) = "cdabef" 时，s2 比 s1 少一个子串 gg，多一个子串 ed。将 s2 相对于 s1 的变化应用到 state1 上，我们得到 state2：s2 达成了串联子串的条件 —— 使用了 words 中所有的单词，不多也不少。

为什么 s1 到 s2 要移动 n2 距离？—— 因为串联子串是 words 的排列，而 words[i].length 为 n2， 不移动 n2 距离，没法复用结果。

回到这道题本身，我们想要求出所有串联子串的开始索引。一共有多少个初始状态？—— n2 个：s[0: n * n2)，s[1: n * n2 + 1)，……，s[n2 - 1: n * (n2 + 1) - 1)。之后的所有长度为 n2 * n 的子串都可以从这些初始状态中求出。

下面的问题，就是如何高效地记录状态、并实现状态转移，让我们结合代码来解决这一问题。

代码

考虑到 words 中可能有重复的 word，我们使用 Map 而不是 Set 来计数：

1
2
3
4
unordered_map<string, int> mp;
for (string & w : words) {
    mp[w]++;
}

然后，我们定义两个 vector，注意观察它们的构造器：

1
2
vector<int> v1(n2, mp.size());
vector<unordered_map<string, int>> v2(n2, mp);

v2 中的每个哈希表记录的是『形成串联子串的 word 的计数情况（即初始的 mp）』与『长度为 n2 * n 的子串中 word 的计数情况』的差值。

v1 记录的是对应哈希表中 value 不为 0 的数量。换句话说，如果 v1 中某元素为 0，则此时对应的 长度为 n2 * n 的子串是一个串联子串。v1 的存在就是为了快速判断是否满足串联子串的条件。

我们以构造初始状态为例，观察这两个 vector 是如何工作的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = 0; i < n2; ++i) {
  	// 判断子串 s[i : i + n * n2) 的状态
    for (int j = 0; j < n; ++j) {
        string s2 = s.substr(i + n2 * j, n2); // 获得第一个长度为 n2 的子串 s2
        int v = --v2[i][s2]; // 修改计数情况
        // 如果 v2[i][s2] > 0，则距离形成串联子串还**缺少** v2[i][s2] 个 s2
        // 如果 v2[i][s2] < 0，则距离形成串联子串还**多出** v2[i][s2] 个 s2
        // 由于在构造初始状态时， v2[i][s2] 只可能减小
        if (v == 0) v1[i]--; // 所以当 v2[i][s2] 为 0 时，v1[i] 要减一
        else if (v == -1) v1[i]++; // 但是当 v2[i][s2] 首次小于 0 时，v1[i] 反而要加一，因为此时来自子串的 word 反而变得多余了
    }

    if (v1[i] == 0) { // 此时达成了串联子串的条件，记录到结果集中
        ans.push_back(i);
    }
}

之后，我们要不断地对初始状态做状态转移，其过程与构造初始状态类似，只不过多出了添加 word 的情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (int i = n2; i + n2 * n <= s.size(); ++i) { // 注意循环中止条件
    // 注意 v2 的定义，这里要做加一操作
    string oldStr = s.substr(i - n2, n2);
    int v = ++v2[i % n2][oldStr]; // 别忘了对 n2 取模
    if (v == 0) v1[i % n2]--;
    else if (v == 1) v1[i % n2]++;

    string newStr = s.substr(i + n2 * (n - 1), n2);
    v = --v2[i % n2][newStr];
    if (v == 0) v1[i % n2]--;
    else if (v == -1) v1[i % n2]++;

    if (v1[i % n2] == 0) { // 此时达成了串联子串的条件，记录到结果集中
        ans.push_back(i);
    }
}

因此，最终的代码是：

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
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int n = words.size(), n2 = words[0].size();
        
        unordered_map<string, int> mp;
        for (string & w : words) {
            mp[w]++;
        }

        vector<int> v1(n2, mp.size());
        vector<unordered_map<string, int>> v2(n2, mp);

        vector<int> ans;

        if (s.size() < n * n2) { // 唯一一个 corner case
            return ans;
        }

        for (int i = 0; i < n2; ++i) {
            for (int j = 0; j < n; ++j) {
                string s2 = s.substr(i + n2 * j, n2);
                int v = --v2[i][s2];
                if (v == 0) v1[i]--;
                else if (v == -1) v1[i]++;
            }

            if (v1[i] == 0) {
                ans.push_back(i);
            }
        }

        for (int i = n2; i + n2 * n <= s.size(); ++i) {
            string oldStr = s.substr(i - n2, n2);
            int v = ++v2[i % n2][oldStr];
            if (v == 0) v1[i % n2]--;
            else if (v == 1) v1[i % n2]++;

            string newStr = s.substr(i + n2 * (n - 1), n2);
            v = --v2[i % n2][newStr];
            if (v == 0) v1[i % n2]--;
            else if (v == -1) v1[i % n2]++;

            if (v1[i % n2] == 0) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};

时间复杂度：O(n * n2 * n2 + s.size() * n2)。

空间复杂度：O(n * n2 * n2)，主要是 v2 的开销。

注意到，一个 word 长度为 n2，因此其空间开销是 O(n2)，而从 s 中获取一个 word 的时间开销也是 O(n2)。