주제 시리즈: Substring with Concatenation of All Words

 public class Solution {

    public ArrayList<Integer> findSubstring(String S, String[] L) {

        //http://www.cnblogs.com/springfor/p/3872516.html

        ArrayList<Integer> res = new ArrayList<Integer>();

        if(S==null || L==null || S.length()==0 || L.length==0 ||L[0].length()==0)  return res;

        HashMap<String, Integer> dict = new HashMap<String, Integer>();

        int wl = L[0].length();

        

        for(String i: L){

            if(dict.containsKey(i)){

                dict.put(i, dict.get(i)+1);

            }else

                dict.put(i, 1);

        }

        

        for(int i=0; i<wl; i++){ 

            int ind = i;  // window's starting index

            int cnt = 0;                        // check how many words included in the window, and it should not be more than L's length 

            HashMap<String, Integer> curdic = new HashMap<String, Integer>();

          // for(int j = 0; j<S.length()-wl; j+=wl){ // check all words in S

              for(int j = i; j<=S.length()-wl; j+=wl){

                String curwd = S.substring(j, j+wl);

                if(!dict.containsKey(curwd)){ // means there is no such word in L, clear curdic and move on(Concatenation must be continuous),

                    curdic.clear();

                    cnt=0;

                    ind = j+wl;

                }else{

                    if(!curdic.containsKey(curwd)){

                        curdic.put(curwd, 1);

                    }else{

                        curdic.put(curwd,curdic.get(curwd)+1);

                    }

                

                // is the window curdic overflow? now check cnt

                    if(curdic.get(curwd)<=dict.get(curwd)){

                        cnt++;

                    }else{

                         while(curdic.get(curwd)>dict.get(curwd)){ // slide the window and remove the words(tmp) till curwd

                             String tmp = S.substring(ind, ind+wl);

                                curdic.put(tmp, curdic.get(tmp)-1);

                                ind += wl;

                                if(curdic.get(tmp)<dict.get(tmp))

                                    cnt--;

                        }

                    }

                        // is cnt already == L? which means the window has all L's words

                    if(cnt==L.length){

                         res.add(ind);

                         String tmp = S.substring(ind, ind+wl);

                         curdic.put(tmp, curdic.get(tmp)-1);

                         ind += wl;

                         cnt--;   //     cnt   ，     i   ，window curdic   ，cnt             

                    }

                }

            }

        }

        return res;

    }

}