Question
You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
Stats
| Frequency | 1 |
| Diffficulty | 3 |
| Adjusted Difficulty | 4 |
| Time to use | ---------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Analysis
There are 2 ways to solve this question.
The naive approach takes around 1200ms to pass, and the KPM-like approach takes around half of that time. Both methods are explained well in this blog.
I will cover only the naive approach.
Naive approach
The naive approach uses a HashMap for 2 reasons. Reason 1 is because there can be duplications in L, and reason 2 is the searching is faster. For information on HashMap, refer to [Fundamental] Recap on Java HashMap.
Time complexity of this solution is O((n - k * m) x m), and space is the size of list L, O(m). If m is not very big, the time can be regarded as O(n).
My code
public class Solution {
public List<Integer> findSubstring(String S, String[] L) {
List<Integer> ans = new ArrayList<Integer>();
if (L == null || L.length == 0 || S == null || S.length() == 0) {
return ans;
}
int num = L.length;
int len = L[0].length();
if (num * len > S.length()) {
return ans;
}
// build a hashset, for simplifying the hashmap generation later on
HashMap<String, Integer> set = new HashMap<String, Integer>();
for (String str: L) {
if (set.containsKey(str)) {
set.put(str, set.get(str) + 1);
} else {
set.put(str, 1);
}
}
// starting from i, check Concatenation of All Words
for (int i = 0; i <= S.length() - (num * len); i++) {
// first build a HashMap from the set that we acquired before
HashMap<String, Integer> map = new HashMap<String, Integer>(set);
for (int j = 0; j < num; j++) {
String str = S.substring(i + j * len, i + (j + 1) * len);
if (!map.containsKey(str)) {
break;
} else if (map.get(str) > 1) {
map.put(str, map.get(str) - 1);
} else if (map.get(str) == 1) {
map.remove(str);
}
}
if (map.isEmpty()) {
ans.add(i);
}
}
return ans;
}
}