Substring with Concatenation of All Words

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


Naive Way: brute force 的方法将是每一个字符的遍历，看它所引领的字符串是否为字典所组成。假设|S| = n, |L| = m, |L[0]| = k，这样的算法复杂度是O(nm)。

而我的基本的想法是隔着一个单词长度的遍历，用一个queue控制进出，然后用一个map装入L的信息，一旦queue.size() == L.length 说明找到一个match。

 如果出现这种情况 L:["foo","bar","arf"...]，说明一个substring即使在字典中找到，也不可以一个单词一个单词的向后递增。

假设每个单词长度是k，任然可以用上述方法，需要为每一个间隔都设置一个queue和一个map。然后每个间隔单独执行以上算法，这样就需要k个queue和k各map。算法复杂度是O(n)。
我觉得这个算法复杂度真心足够了。

有一个容易出错的地方是当map不包含当前word时，可能queue出来的那个正好等于当前word，此时，要做的就是不改变map，把当前word推进queue，然后queue再排出最前面的word。

算法复杂度是O(n), space O(km)

 public class Solution {  
   public List<Integer> findSubstring(String S, String[] L) {  
     List<Integer> rslt = new ArrayList<Integer>();  
     // edge case  
     if(L.length==0) return rslt;  
     // initialize k queues and k maps  
     int k = L[0].length();  
     List<Queue<String>> queues = new ArrayList<Queue<String>>();  
     List<Map<String, Integer>> maps = new ArrayList<Map<String, Integer>>();  
     Map<String, Integer> map_temp = new HashMap<String, Integer>();  
     for(int i = 0;i < L.length;i++) setMap(map_temp, L[i]);  
     for(int i = 0;i < k;i++) queues.add(new LinkedList<String>());  
     for(int i = 0;i < k;i++) maps.add(new HashMap<String, Integer>(map_temp));  
     // go though S  
     for(int i = 0;i <= S.length()-k;i++){  
       Queue<String> queue = queues.get(i%k);  
       Map<String, Integer> map = maps.get(i%k);   
       String s = S.substring(i,i+k);  
       if(map.containsKey(s)){  
         queue.add(s);  
         map.put(s,map.get(s)-1);  
         if(map.get(s)==0) map.remove(s);  
       }else{  
         if(!queue.isEmpty()){  
           if(s.equals(queue.peek())) // when the word to be poll == the word to be add  
             queue.add(queue.poll()); // don't need to modify map  
           else  
             while(!queue.isEmpty()) setMap(map, queue.poll());  
         }  
       }  
       // find a match  
       if(queue.size()==L.length){  
         rslt.add(i-(L.length-1)*k);  
         setMap(map,queue.poll());  
       }  
     }  
     return rslt;  
   }  
   private void setMap(Map<String, Integer> map, String s){  
     if(!map.containsKey(s))  
       map.put(s,1);  
     else  
       map.put(s,map.get(s)+1);  
     return;  
   }  
 }  

Improved Way: 我看了https://oj.leetcode.com/discuss/20151/an-o-n-solution-with-detailed-explanation这个算法后发现queue完全可以用一个变量来代替，记录长度即可。

 public class Solution {  
   public List<Integer> findSubstring(String S, String[] L) {  
     List<Integer> rslt = new ArrayList<Integer>();  
     // edge case  
     if(L.length==0) return rslt;  
     // initialize k queues and k maps  
     int k = L[0].length();  
     int queues[] = new int[k];  
     List<Map<String, Integer>> maps = new ArrayList<Map<String, Integer>>();  
     Map<String, Integer> map_temp = new HashMap<String, Integer>();  
     for(int i = 0;i < L.length;i++) setMap(map_temp, L[i]);  
     for(int i = 0;i < k;i++) queues[i] = 0;  
     for(int i = 0;i < k;i++) maps.add(new HashMap<String, Integer>(map_temp));  
     // go though S  
     for(int i = 0;i <= S.length()-k;i++){  
       int queue = queues[i%k];  
       Map<String, Integer> map = maps.get(i%k);   
       String s = S.substring(i,i+k);  
       if(map.containsKey(s)){  
         queue++;  
         map.put(s,map.get(s)-1);  
         if(map.get(s)==0) map.remove(s);  
         // find a match  
         if(queue==L.length){  
           rslt.add(i-(queue-1)*k);  
           setMap(map, S.substring(i-k*(queue-1),i-k*(queue-1)+k));  
           queue--;  
         }  
       }else{  
         if(queue > 0){  
           if(!s.equals(S.substring(i-k*queue,i-k*queue+k)))  
             while(queue > 0){  
               setMap(map, S.substring(i-k*queue,i-k*queue+k));  
               queue--;  
             }  
         }  
       }  
       queues[i%k] = queue;  
     }  
     return rslt;  
   }  
   private void setMap(Map<String, Integer> map, String s){  
     if(!map.containsKey(s))  
       map.put(s,1);  
     else  
       map.put(s,map.get(s)+1);  
     return;  
   }  
 }