Monday, May 26, 2014

Substring with Concatenation of All Words

Actually, the basic idea is to check each substring of size strLen* S.length to see whether it is concatenated by each word in the list

public class Solution {
    public ArrayList<Integer> findSubstring(String S, String[] L) {
        if(S == null || L == null){
            return null;
        }
        int strLen = L[0].length();
        if (strLen == 0) return null;
        HashMap<String,Integer> wordsMap = new HashMap<String,Integer>();
        ArrayList<Integer> resultIdx = new ArrayList<Integer>();
        initialMap(wordsMap,L);// store the frequency of each word in the String[] L
     
        for(int i = 0;i <= S.length() - strLen * L.length;i ++){//if one substring of S is composed of each word in //L, this substring must be length of strLen* L.length, so I just need to check each substring of size strLen* //L.length
            String currentStr = S.substring(i,i+strLen * L.length);
            if(check(currentStr,wordsMap,strLen)) {
               
                resultIdx.add(i);
            }
                initialMap(wordsMap,L);
           
        }
       
        return resultIdx;
    }
   
    public void initialMap(HashMap<String, Integer> wordsMap, String[] L){
       
        wordsMap.clear();
        for(int i = 0; i < L.length; i ++) {
        if(!wordsMap.containsKey(L[i])) wordsMap.put(L[i],1);
        else {
                int val = wordsMap.get(L[i]);
                val ++;
                // wordsMap.remove(L[i]);
                wordsMap.put(L[i],val);
            }  
        }
    }
   
    public boolean check(String currentStr, HashMap<String, Integer> wordsMap, int strLen){
       
        for(int i = 0;i <= currentStr.length() - strLen;i += strLen){
            String cmpntStr = currentStr.substring(i,i+ strLen);
            if(wordsMap.containsKey(cmpntStr)){
                int val = wordsMap.get(cmpntStr);
                val--;
                if(val < 0) return false;
                wordsMap.put(cmpntStr,val);
            }
            else{
                return false;
            }
        }
        return true;
    }
   
    public boolean determineAllWordsChecked(HashMap<String,Integer> wordsMap){
        for (Integer count: wordsMap.values()){
            if(count != 0) return false;
        }
        return true;
    }
}

No comments:

Post a Comment