2022.6.23-----leetcode.30

  public List<Integer> findSubstring(String s, String[] words) {
        int len=s.length();
        int m=words[0].length();
        int n= words.length;
        Map<String,Integer> map=new HashMap<>();//存储单词及其数量
        List<Integer> ans=new ArrayList<>();
        for(String word:words){
            map.put(word,map.getOrDefault(word,0)+1);
        }
        //枚举m*n长度的子串,起点由[0,m-1],每个起点的右移步长为m
        for (int i = 0; i <m; i++) {
            Map<String, Integer> map1=new HashMap<>();//存储子串的单词
            //记录初始单词
            for (int j = i; j +m<=Math.min(len,i+m*n) ; j+=m) {
                String tmp=s.substring(j,j+m);
                map1.put(tmp,map1.getOrDefault(tmp,0)+1);
            }
            if(map1.equals(map)) ans.add(i);
            String l="";
            String r="";
            //每次右移,添加新单词,去掉旧单词
            for (int j = i; j +m*n+m<=len ; j+=m) {
                l=s.substring(j,j+m);
                r=s.substring(j+m*n,j+m*n+m);
                if(map1.get(l)==1) map1.remove(l);
                else map1.put(l,map1.get(l)-1);
                map1.put(r,map1.getOrDefault(r,0)+1);
                if(map1.equals(map)) ans.add(j+m);

            }
        }
        return ans;
    }