LeetCode30Substring-with-Concatenation-of-All-Words

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.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”] Output:
[0,9] Explanation: Substrings starting at index 0 and 9 are “barfoor”
and “foobar” respectively. The output order does not matter, returning
[9,0] is fine too. Example 2:

Input: s = “wordgoodgoodgoodbestword”, words =
[“word”,”good”,”best”,”word”] Output: []

思路是通过 indexOf 找到最靠前的那个，然后通过每个数组判读是不是符合情况。这样想起来很乱
应该是先在脑海中构建出暴力解法，也就是当 index 到 i 时，判断 i 之前加上 i 之前的情况是否满足条件。i 之前的情况可以提前保存下来，达到优化的目的。
还有考察点就是数据结构，这个结构需要满足查询是 o1, 且能保留加入的顺序，最开始我们采用的结构式 LinkedHashSet，但是没有注意到 words 里的顺训是可以重复的.
可以整理下我们需要的数据结构
1. 能保留添加顺序
2. 可以判断是不是无顺序的
可以使用 LinkedHashMap
但是对他的 equals 不是很满意
还有无法知道他包含元素的个数，需要另外一个数组保存
后来否定了这个思路，这样会有一个 Bug，LinkedHashMap 添加两次相同数据后，第二次添加时候的顺序反应的是不准确的
还是使用两个数据结构，一个 LinkedList 和 HashMap

public List<Integer> findSubstring(String s, String[] words) {List<Integer> list=new ArrayList();
        int a=words.length;
        if(a<=0) return list;
        int b=words[0].length();
        if(b<=0) return list;
        int len=s.length();
        HashMap<String,Integer> target=new HashMap();
        for(String s1:words) target.compute(s1,(k,v)->v==null?1:v+1);
        LinkedList[] linkeds=new LinkedList[len];
        HashMap[] maps=new HashMap[len];
        for(int i=0;i<=len-b;i++){
            LinkedList<String> linked;
            HashMap<String,Integer> map;
            if(i>=b){linked=linkeds[i-b];
                map=maps[i-b];
                if(linked.size()>=a) {String first=linked.removeFirst();
                    if(map.get(first)>1) map.put(first,map.get(first)-1);
                    else map.remove(first);
                }
            }else{linked=new LinkedList();
                map=new HashMap();}
            String s1=s.substring(i,i+b);
            if(target.containsKey(s1)){linked.addLast(s1);
                map.compute(s1,(k,v)->v==null?1:v+1);
            }else{map.clear();
                linked.clear();}
            if(map.equals(target)) list.add(i-(a-1)*b);
            linkeds[i]=linked;
            maps[i]=map;
        }
        return list;
}