LeetCode30-串联所有单词的字串

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/substring-with-concatenation-of-all-words/

中文链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words/

题目详述

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

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

示例 1：

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

示例 2：

1
2
3
4
输入：
  s = "wordgoodgoodgoodbestword",
  words = ["word","good","best","word"]
输出：[]

题目详解

滑动窗口，思想类似于 LeetCode438-找到字符串中所有字母异位词。

  • 之前对单个字符进行存储，向右滑动一个长度；这次对单词进行存储，向右滑动一个单词长度。
  • 由于是滑动一个单词长度（记为 len），起始位置的可能区间为 [0, len) 。
  • 由于每一轮窗口滑动会对 map 进行改动，所以进入本轮前复制一次 map。
  • 时间复杂度为 O(n * len)。
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
52
public class LeetCode_00030 {

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0 || s.length() < words.length * words[0].length()) {
            return res;
        }
        Map<String, Integer> src = new HashMap<>();
        for (String word : words) {
            src.put(word, src.getOrDefault(word, 0) + 1);
        }
        int len = words[0].length();
        int window = words.length * len;
        // 分别从 [0, len) 开始寻找
        for (int i = 0; i < len; ++i) {
            // 复制一份，避免上次循环对这次的干扰
            Map<String, Integer> map = new HashMap<>(src);
            // 初始化 size 为当前单词数量
            int size = words.length;
            // 窗口 [l, r) 从本次起始位置 i 开始
            int l = i, r = i;
            while (r + len <= s.length()) {
                String sub = s.substring(r, r + len);
                r += len;
                if (map.containsKey(sub)) {
                    // 对应计数减一
                    map.put(sub, map.get(sub) - 1);
                    // 在有效范围内更新 size
                    if (map.get(sub) >= 0) {
                        --size;
                    }
                }
                while (size == 0) {
                    if (r - l == window) {
                        res.add(l);
                    }
                    sub = s.substring(l, l + len);
                    l += len;
                    if (map.containsKey(sub)) {
                        // 对应计数减一
                        map.put(sub, map.get(sub) + 1);
                        // 在有效范围内更新 size
                        if (map.get(sub) > 0) {
                            ++size;
                        }
                    }
                }
            }
        }
        return res;
    }
}
  • 也可以每一轮构建一个空的 map，在空的 map 上进行操作，避免复制，提高效率。
  • 这样的话对应的 size 更新条件也要随之更改。
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
public class LeetCode_00030 {

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (words.length == 0 || s.length() < words.length * words[0].length()) {
            return res;
        }
        Map<String, Integer> src = new HashMap<>();
        for (String word : words) {
            src.put(word, src.getOrDefault(word, 0) + 1);
        }
        int len = words[0].length();
        int window = words.length * len;
        for (int i = 0; i < len; ++i) {
            // 构建一个空的 HashMap
            Map<String, Integer> map = new HashMap<>();
            int size = words.length;
            int l = i, r = i;
            while (r + len <= s.length()) {
                String sub = s.substring(r, r + len);
                r += len;
                if (src.containsKey(sub)) {
                    map.put(sub, map.getOrDefault(sub, 0) + 1);
                    // 在有效范围内更新 size
                    if (map.get(sub) <= src.get(sub)) {
                        --size;
                    }
                }
                while (size == 0) {
                    if (r - l == window) {
                        res.add(l);
                    }
                    sub = s.substring(l, l + len);
                    l += len;
                    if (src.containsKey(sub)) {
                        map.put(sub, map.get(sub) - 1);
                        // 在有效范围内更新 size
                        if (map.get(sub) < src.get(sub)) {
                            ++size;
                        }
                    }
                }
            }
        }
        return res;
    }
}