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;
}
}
Hello, welcome to Yizhe's Blog. I am Yizhe Liu, graduated from University of Arizona, with Master degree, major in Electrical and Computer Engineering. Actually, I am software guy. In my blog, many posts are about the Leetcode questions. I will post my ideas and implementations, which are accepted by Leetcode. If you have different opinions, please leave comment. I am happy to discuss with you. So lets start rocking them!!!
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.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment