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.
Input:
s = "barfoothefoobarman",
words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoor" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Input:
s = "wordgoodstudentgoodword",
words = ["word","student"]
Output: []
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
if (s == null || words == null || words.length == 0 ) {
return ans;
}
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
if (map.containsKey(word)) {
map.put(word, map.get(word) + 1);
}else{
map.put(word,1);
}
}
int n = words.length;
int m = words[0].length();
for (int i = 0; i <= s.length() - n * m; i++) {
Map<String, Integer> copy = new HashMap<>(map);
int j = i;
int count = n;
while (count > 0) {
String temp = s.substring(j, j+m);
if (!copy.containsKey(temp) || copy.get(temp) < 1) {
break;
}
copy.put(temp, copy.get(temp) - 1);
count--;
j = j + m;
}
if (count == 0) {
ans.add(i);
}
}
return ans;
}
}