My 16 ms Java solution


  • 0
    Y

    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.
                        res.add(start);
                    }
                    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]--;
            }
        }
    }

Log in to reply
 

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