leetcode30.串联所有单词的子串

Posted on | In |
Words count in article: 895 | Reading time ≈ 3

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

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

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

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

示例：

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] 也是可以的。

分析：

1
2
3
4
5
6
一种比较简单的暴力做法是枚举s的每个位置，然后考虑以该位置为起点是否存在一个由words里所有单词拼接而成的字符串，由于每个word长度相同，可以利用哈希表，一个单词一个单词的来枚举，看最后是否用完了words里的单词并且中间不存在不合法的单词。这样的复杂度为O(n∗w∗m)，n为字符串s的长度，w是单词的长度，m是单词列表words的长度。不过这个做法会超时。

下面我们考虑怎么优化这个做法，因为有单词长度都相同这个限制，问题可以转化成将字符串s切成每段长度为w的序列，那么不同的序列最多有多少个（长度不足w的抛弃）？答案是w个，从起点0,1,2,...,w-1开始最多可以有w个不同的单词序列，从w开始的序列和从0开始的是等价的。

所以我们就可以枚举每个序列，对于每个序列我们可以用双指针来搜索包含words所有单词的连续序列。这里是以单词为单位进行双指针移动，双指针的思路类似于LeetCode 3. Longest Substring Without Repeating Characters ， 我们每次将窗口右端的单词加入哈希表，如果它的个数大于words中的个数，当前序列肯定不合法，我们不断地移动左端点使得窗口再次合法，当窗口长度为m时说明我们找到了一个答案。
共有w个序列，每次枚举序列需要O(n)的复杂度，总时间复杂度为O(n∗w)，比暴力做法优化掉了单词列表长度m.

代码

  • C++

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

        for (int i = 0;i < w;i ++) {
            unordered_map<string, int> window;
            int num = 0;
            for (int j = i;j + w <= n;j += w) {
                if (j >= i + m * w) {
                    string word = s.substr(j - m * w, w);
                    window[word] --;
                    if (window[word] < cnt[word]) num --;
                }
                string word = s.substr(j, w);
                window[word] ++;
                if (window[word] <= cnt[word]) num ++;
                if (num == m) res.push_back(j - (m - 1) * w);
            }
        }

        return res;
    }
};

[原题链接](30. 串联所有单词的子串 - 力扣（Leetcode）)

0%