# My 16 ms Java solution

• I didn't use anything fancy, just the same "shifting window" solution like others.

The only thing is, cloning the hash map, or adding/removing entries from it could be a little time consuming, so I just created an inner class Node, which stores the original value for each hash map entry. When we start a new series of windows, we just do the calculation based on "origin" instead of "val", which saves a little time.

``````public class Solution {
class Node {
int start;
int origin;
int val;
public Node(int ori) {
start = -1;
origin = ori;
}
}
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new ArrayList<>();
if(s == null || words == null || s.length() == 0 || words.length == 0 || words[0].length() == 0) {
return res;
}
int wordLen = words[0].length();
int listLen = wordLen * words.length;
HashMap<String, Node> map = new HashMap<>(words.length);
for(String word : words) {
if(map.containsKey(word)) {
Node node = map.get(word);
node.origin++;
} else {
map.put(word, new Node(1));
}
}
int target = map.size();
for(int i=0;i<wordLen;i++) {
if(i+listLen > s.length()) break;
int[] zeroCount = new int[]{0};
int start = i;
// process the initial words.length words
for(int j=i;j<=i+listLen-wordLen;j+=wordLen) {
setWord(map.get(s.substring(j, j+wordLen)), zeroCount, true, i);
}
while(start + listLen <= s.length()) {
if(zeroCount[0] == target) {
// every node val in the hashMap is 0, which means an exact match.
}
if(start+listLen+wordLen <= s.length()) {
// shift the window, remove a word from the left and add a word on the right.
setWord(map.get(s.substring(start, start+wordLen)), zeroCount, false, i);
setWord(map.get(s.substring(start+listLen, start+listLen+wordLen)), zeroCount, true, i);
}
start+=wordLen;
}
}
return res;
}

public void setWord(Node node, int[] count, boolean isAddWord, int start) {
if(node != null) {
int delta = isAddWord ? -1 : 1;
if(node.start == start) {
// the same series of windows, continue iterating node.val
node.val = node.val + delta;
} else {
// a different series of windows, calculate based on origin
node.val = node.origin + delta;
node.start = start;
}
if(node.val == 0) count[0]++;
else if(node.val == delta) count[0]--;
}
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.