Substring with Concatenation of All Words (hard) leetcode

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 wordsexactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

题意：给定一个字符串S和一个字符串数组L，L中的字符串长度都相等，找出S中所有的子串恰好包含L中所有字符各一次，返回子串的起始位置。

用一个hashmap把words里面所有单词放入, 出现次数为单词的value 作为字典

再用另一个hashmap 记录当前单词

因为每个单词长度一样，外层循序只许循环wordLen次，每次指针挪一次，每一次循环遍历整个字符串。

内层循环每次遍历一个单词，把整个S字符串遍历检查。

需要在每次大循环维护一个count，看是不是达到了给的字典字符串数量，同时维护一个index，是每个符合条件的字符串的起始index，需要存到返回结果中。

为了能够检查是不是合格字符串，在这里维护一个curDict的HashMap。



首先检查一个单词是不是在原始字典中出现，没出现的话说明这个单词肯定不符合标准，index指针指向下一个单词的起始点，计数器和curDict都要清零。


如果这个单词在原始字典里出现过，用更新原始字典的方法更新curDict，如果这个单词出现的次数没有超过原始字典里记录的次数，那么count++，如果超过了，就需要挪动指针，并把超过的从curDict删掉。


最后，如果count达到了L的length，说明找到了一个合格的字符串，那么将index存入返回结果res中，再把index挪到下一个单词处，更新curDict即可。

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        int m = words.length;
        int n = words[0].length();
        ArrayList<Integer> result = new ArrayList<Integer>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        for (int i = 0; i < m; i++) {//把words所有单词放入map里
            if (map.containsKey(words[i])) {
                map.put(words[i], map.get(words[i]) + 1);
            } else {
                map.put(words[i], 1);
            }
        }
        for (int i = 0; i < n; i++) {
            int count = 0;
            int left = i;
            HashMap<String, Integer> curmap = new HashMap<String, Integer>();
            for (int j = i; j <= s.length() - n; j += n) {
                String str = s.substring(j, j + n);
                if (!map.containsKey(str)) {
                    left = j + n;
                    curmap.clear();
                    count = 0;
                } else {
                    if (!curmap.containsKey(str)) {
                        curmap.put(str, 1);
                    } else {
                        curmap.put(str, curmap.get(str) + 1); 
                    }
                    if (curmap.get(str) <= map.get(str)) {//如果当前和map中都有这个单词 count++
                        count++;
                    } else {//如果这个单词出现次数>map中出现的次数
                        while (curmap.get(str) > map.get(str)) {
                            String tem = s.substring(left, left + n);

                            curmap.put(tem, curmap.get(tem) - 1);
                            if(curmap.get(tem)<map.get(tem)) {//如果是= 说明tem就是str 对于str并没有在count中+
                                count--;
                            } 
                            
                            left = left + n;
                        }
                    }
                    if (count == m) {
                        result.add(left);
                        String tem = s.substring(left, left + n);
                        curmap.put(tem, curmap.get(tem) - 1);
                        count--;
                        left += n;
                    }
                }
            }
        }
        return result;
    }
}