30 Substring with Concatenation of All Words

1. Question

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).

2. Implementation

(1) Two Pointers + Hash
1
class Solution {
2
public List<Integer> findSubstring(String s, String[] words) {
3
int n = words.length, wordLen = words[0].length();
4
List<Integer> res = new ArrayList<>();
5
Map<String, Integer> map = new HashMap<>();
6
Map<String, Integer> seen = new HashMap<>();
7
8
for (String word : words) {
9
map.put(word, map.getOrDefault(word, 0) + 1);
10
}
11
12
for (int i = 0; i <= s.length() - wordLen * n; i++) {
13
seen = new HashMap<>();
14
int j = 0;
15
16
for (; j < n; j++) {
17
String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
18
19
if (!map.containsKey(word)) {
20
break;
21
}
22
23
seen.put(word, seen.getOrDefault(word, 0) + 1);
24
if (seen.get(word) > map.get(word)) {
25
break;
26
}
27
}
28
29
if (j == n) {
30
res.add(i);
31
}
32
}
33
return res;
34
}
35
}
Copied!

3. Time & Space Complexity

Two Pointers: 时间复杂度O(mn), m为s的长度,n为words里word的个数,空间复杂度O(n)