题目：

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].

(order does not matter).

题意：

给定一个字符串s, 和一组字符串数组words,数组中的全部字符串长度都一样。从字符串s中找出全部子串的開始标号。这些子串是words中全部字符串的组合。而且每一个字符串仅仅出现一次且没有其它字符插入他们之间，这些字符串的排列顺序无所谓。

算法分析：

方法一：

  *  由于L中全部单词的长度是一样的。这样依据wordLen。能够将S分为wordLen组，实际意思是这种。

  *  以题目中barfoothefoobarman举例，L中单词长度为3。能够分为

  *  bar|foo|the|foo|bar|man

  *  ba|rfo|oth|efo|oba|rma|n

  *  b|arf|oot|hef|oob|arm|an    

  *  这样。针对每一个分组，能够利用最小滑动窗体的思想，高速的推断是否包括须要的字符串。

  *  直观上来看，是须要从每一个字符開始搜索，实际上，利用两个指针去在S中寻找满足条件的字符串，并且是每次+wordLen。并且不会反复的去统     *  计。节省

  *  了非常多时间。

方法二：

  思路仍然是维护一个窗体。如果当前单词在字典中，则继续移动窗体右端。否则窗体左端能够跳到字符串下一个单词了。如果源字符串的长度为n。字典中单词的长度为l。由于不是一个字符。所以我们须要对源字符串全部长度为l的子串进行推断。

每次按顺序在源字符串中截取和字典中全部字符串长度相等的长度，推断新截取的子串和字典中字符串是否匹配，匹配就增加到结果中。不匹配就依次继续在源字符串中截取新的子串。反复上述过程直到结束。

AC代码：

方法一：

public class Solution{    public ArrayList
      
        findSubstring(String S, String[] L)     {        ArrayList
       
         list = new ArrayList
        
         ();		int len = L.length;		if (len == 0) 			return list;					int wordLen = L[0].length();		Map
         
           wordsMap = new HashMap
          
           (); for (int i = 0; i < len; i++) { int num = 1; if (wordsMap.get(L[i]) != null) num += wordsMap.get(L[i]); wordsMap.put(L[i], num); } int slen = S.length(); int max = slen - wordLen + 1; for (int i = 0; i < wordLen; i++) { Map
           
             numMap = new HashMap
            
             (); int count = 0; int start = i; for (int end = start; end < max; end += wordLen) { String tempStr = S.substring(end, end + wordLen); if (!wordsMap.containsKey(tempStr))//给定字符串数组中不包括当前的字符串，直接跳到下一个字符串 { numMap.clear(); count = 0; start = end + wordLen; continue; } int num = 1; if (numMap.containsKey(tempStr)) num += numMap.get(tempStr); numMap.put(tempStr, num); if (num <= wordsMap.get(tempStr)) count++;//仅仅有在小于给定数组元素个数的情况下才自加 else { while (numMap.get(tempStr) > wordsMap.get(tempStr)) { tempStr = S.substring(start, start + wordLen);//在如今的map尾部中出现大于给定数组元素个数的情况是时，去除map头部元素 numMap.put(tempStr, numMap.get(tempStr) - 1); if (numMap.get(tempStr) < wordsMap.get(tempStr)) count--;//去除了元素了。个数自来就少了一个 start += wordLen;//相应的起始元素也往后移动了一个 } } if (count == len) { list.add(start); tempStr = S.substring(start, start + wordLen);//满足条件后去除头个元素，也就是又一次后移一个位置，看看后面的满足条件不 numMap.put(tempStr, numMap.get(tempStr) - 1); count--; start += wordLen; } } } return list; }}
            
           
          
         
        
       
      

方法二：

public class Solution {    public List
     
       findSubstring(String S, String[] L)     {        List
      
        result=new ArrayList
       
        ();        if(L.length==0||S.length()==0) return result;        int wordlen=L[0].length();        //map中存放L        HashMap
        
          map=new HashMap
         
          ();        for(int i=0;i
          
            S.length()) { break; } if(map.containsKey(S.substring(i,i+wordlen))) { boolean b=checkString(S.substring(i,i+wordlen*L.length),new HashMap
           
            (map),wordlen); if(b==true) result.add(i); } } return result; } //检查字符串S是不是map中字符串的组合 public boolean checkString(String s,HashMap
            
              map,int wordlen) { boolean flag=true; int i=0; while(s.length()>0) { String temp=s.substring(0,wordlen); Integer value=map.get(temp); if(value==null||value==0) { flag=false; break; }else{ value-=1; map.put(temp,value); s=s.substring(wordlen);//该子字符串从指定索引处的字符開始，直到此字符串末尾。 } } return flag; }}