java solution using slide window


  • 0
    W
    public List<Integer> findSubstring(String s, String[] words) {
           int lenOfWord = words[0].length();
    		int len = words.length;
    		List<Integer> list = new ArrayList<>();
    		Map<String, Integer> map = new HashMap<>();
    		for (String a : words) {
    			map.put(a, map.containsKey(a) ? map.get(a) + 1 : 1);
    		}
    		for (int i = 0; i < lenOfWord; i++) {
    			Map<String, Integer> window = new HashMap<>();
    			int left = i, right = i;
    			while (right <= s.length() - lenOfWord) {
    				String word = s.substring(right, right + lenOfWord);
    				right += lenOfWord;
    				if (map.containsKey(word)) {
    					window.put(word, window.containsKey(word) ? window.get(word) + 1 : 1);
    					while (window.get(word) > map.get(word)) {
    						String head = s.substring(left, left + lenOfWord);
    						left += lenOfWord;
    						window.put(head, window.get(head) - 1);
    					}
    				} else {
    					window.clear();
    					left = right;
    				}
    				if (right - left == len * lenOfWord) {
    					list.add(left);
    					window.clear();
    					left += lenOfWord;
    					right = left;
    				}
    			}
    		}
    		return list;
    

Log in to reply
 

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