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