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.
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
(order does not matter).
Solution
Slide-window + HashMap, time O(n * m), space O(1)
首先将words缓存在HashMap中，然后遍历s，把每个i作为startIndex开始，往后面尽量扩展即可。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> startIdx = new ArrayList<>();
int targetLen = 0;
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
targetLen += word.length();
map.put(word, map.getOrDefault(word, 0) + 1);
}
if (s.length() < targetLen || words.length == 0) {
return startIdx;
}
int wordLen = words[0].length();
for (int i = 0; i <= s.length() - targetLen; ++i) {
Map<String, Integer> need = new HashMap<>(map);
boolean isValid = true;
for (int j = i; j < i + targetLen; j += wordLen) {
String curr = s.substring(j, j + wordLen);
if (need.getOrDefault(curr, 0) == 0) {
isValid = false;
break;
}
need.put(curr, need.get(curr) - 1);
}
if (isValid) {
startIdx.add(i);
}
}
return startIdx;
}
}
