LeetCode - Substring with Concatenation of All Words
Problem description
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.
Example 1:
1
2
3
4
5
6
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Example 2:
1
2
3
4
Input:
s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]
Output: []
Analysis
Basic idea is to check one position by one position.
Here’s the code:
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
public class SubstringwithConcatenationofAllWords {
public List<Integer> findSubstring(String s, String[] words) {
int wordSize = words.length;
if (wordSize == 0 || s.isEmpty()) {
return new ArrayList<>();
}
int wordLen = words[0].length();
List<Integer> res = new ArrayList<>();
if (s.length() < wordLen * wordSize) {
return res;
}
HashMap<String, Integer> map = new HashMap<>();
for (int i = 0; i < wordSize; i++) {
map.put(words[i], map.getOrDefault(words[i], 0) + 1);
}
for (int i = 0; i <= s.length() - wordLen * wordSize; i++) {
if (check(
s.substring(i, i + wordLen * wordSize),
(HashMap<String, Integer>) map.clone(),
wordLen)) {
res.add(i);
}
}
return res;
}
boolean check(String str, HashMap<String, Integer> map, int len) {
int index = 0;
while (index != str.length()) {
String s = str.substring(index, index + len);
if (map.containsKey(s)) {
int cnt = map.get(s);
if (cnt == 1) {
map.remove(s);
} else {
map.put(s, cnt - 1);
}
} else {
return false;
}
index += len;
}
return map.size() == 0;
}
}
This method’s performance is not very well, runtime 120 ms, faster than 42.07%.
Here’s the sample code from LeetCode, basic idea is to treat this as a sliding window and this indeed can improve performance:
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
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
if(s.length() == 0 || words.length == 0) return new ArrayList<>();
final Map<String, Integer> need = new HashMap<>();
for (final String word : words) {
need.put(word, need.getOrDefault(word, 0) + 1);
}
final int n = s.length();
final int num = words.length;
final int len = words[0].length();
final List<Integer> ans = new ArrayList<>();
for (int i = 0; i < len; i++) {
int l = i, count = 0;
final Map<String, Integer> seen = new HashMap<>();
for (int j = i; j <= n - len; j += len) {
final String word = s.substring(j, j + len);
if (need.containsKey(word)) {
seen.put(word, seen.getOrDefault(word, 0) + 1);
if (seen.get(word) <= need.get(word)) {
count++;
} else {
while (seen.get(word) > need.get(word)) {
final String first = s.substring(l, l += len);
seen.put(first, seen.getOrDefault(first, 0) - 1);
if (seen.get(first) < need.getOrDefault(first, 0)) {
count--;
}
}
}
if (count == num) {
ans.add(l);
count--;
final String first = s.substring(l, l += len);
seen.put(first, seen.get(first) - 1);
}
} else {
seen.clear();
count = 0;
l = j + len;
}
}
}
return ans;
}
}
What to improve
- think more and do coding.