30. Substring with Concatenation of All Words

发表于 | 分类于

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

解法1：

也是滑动窗口的思路，第一层循环是对于起始点的遍历。起始点可以从0到word的长度－１。
之后就是一个词一个词的向右进。同时统计每一个词出现的次数。
C++

1

Java

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
53
54
55
56
57
public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<Integer>();
        if (words == null || words.length == 0) {
            return res;
        }
        Map<String, Integer> map = new HashMap<>();
        Map<String, Integer> currentMap = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        int len = s.length();
        int N = words.length;
        int M = words[0].length();
        for (int i = 0; i < M; i++) {
            int count = 0;
            int start = i;  // record the start index of the substring
            int left = start, right = left + M;
            while (right <= len) {
                String current = s.substring(left, right);
                if (map.containsKey(current)) {
                    currentMap.put(current, currentMap.getOrDefault(current, 0) + 1);
                    if (currentMap.get(current) <= map.get(current)) count++;    // find a matched word
                    while (currentMap.get(current) > map.get(current)) {
                        String temp = s.substring(start, start + M);
                        currentMap.put(temp, currentMap.get(temp) - 1);
                        start += M; // update the start of the substring
                        if (currentMap.get(temp) < map.get(temp)) count--;
                    }
                    if (count == N) {
                        res.add(start);
                        String temp = s.substring(start, start + M);
                        currentMap.put(temp, currentMap.get(temp) - 1);
                        count--;
                        start += M; // update the start of the substring
                    }
                } else {
                    count = 0;
                    currentMap.clear();
                    start = right;
                }
                left = right;
                right += M;
            }
            currentMap.clear();
        }
        return res;
    }
}