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;}