Tuesday, September 16, 2014

Substring with Concatenation of All Words

Honestly, this question is not very difficult, but its AC rate is not that low. Logic is simple and easy to understand. Check out my code below, and if any questions, please let me know.




 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>();  
     //for(int i = 0; i < L.length; i ++) wordsMap.put(L[i],1);  
     initialMap(wordsMap,L);  
     for(int i = 0;i <= S.length() - strLen * L.length;i ++){  
       String currentStr = S.substring(i,i+strLen * L.length);  
       if(check(currentStr,wordsMap,strLen)) {  
         resultIdx.add(i);  
         //i += strLen * L.length;  
       }  
         //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;  
   }  
 }  

No comments:

Post a Comment