You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:

S: "barfoothefoobarman"

L: ["foo", "bar"]

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

(order does not matter).

使用了 HashMap来降低时间复杂度， 整个的算法很简单。

1 public class Solution { 2      int elen = 0; 3     public ArrayList
     
       findSubstring(String S, String[] L) { 4         // Note: The Solution object is instantiated only once and is reused by each test case. 5         ArrayList
      
        result = new ArrayList
       
        (); 6         if(S == null || S.length() == 0) return result; 7         int slen = S.length(); 8         int n = L.length; 9         elen = L[0].length();10         HashMap
        
          hm = new HashMap
         
          ();11         for(int i = 0; i < n; i ++){12             if(hm.containsKey(L[i])) 13                 hm.put(L[i], hm.get(L[i]) + 1);14             else                     15                 hm.put(L[i], 1);16         }17         for(int i = 0; i <= slen - n * elen; i ++){18             if(hm.containsKey(S.substring(i, i + elen)))19                 if(checkOther(new HashMap
          
           (hm), S, i))20 result.add(i);21 }22 return result;23 }24 public boolean checkOther(HashMap
           
             hm, String s, int pos){25 if(hm.size() == 0) return true;26 if(hm.containsKey(s.substring(pos, pos + elen))){27 if(hm.get(s.substring(pos, pos + elen)) == 1) 28 hm.remove(s.substring(pos, pos + elen));29 else 30 hm.put(s.substring(pos, pos + elen), hm.get(s.substring(pos, pos + elen)) - 1);31 return checkOther(hm, s, pos + elen);32 }33 else return false;34 }35 }