The idea below is very simple, create a count Map for L, and inside S, cut same length as L.size() * L[0].length(). Loop this subString inside S, and compare with the Map for L. If match, add current index, otherwise move to next. index + L * L[0] < S.length()
public class Solution {
public ArrayList<Integer> findSubstring(String S, String[] L) {
if(S == null || L == null ||L.length == 0 || S.length() < (L[0].length() * L.length)){
return new ArrayList<Integer>();
}
//ArrayList<Integer> results = new ArrayList<Integer>();
return findSubstringOps(S, L);
}
private ArrayList<Integer> findSubstringOps(String S, String[] L){
ArrayList<Integer> results = new ArrayList<Integer>();
if(S == null || L == null ||L.length == 0 || S.length() < (L[0].length() * L.length)){
return results;
}
int index = 0;
int wordSize = L[0].length();
while(index <= S.length() - (wordSize * L.length)){
int secondIndex = index;
boolean found = true;
HashMap<String, Integer> process = buildMap(L);
while(secondIndex < index + wordSize * L.length){
String cur = S.substring(secondIndex, secondIndex + wordSize);
if(process.containsKey(cur)){
if(process.get(cur) == 0){
found = false;
break;
}
process.put(cur, process.get(cur) - 1);
secondIndex += wordSize;
}else{
found = false;
break;
}
}
if(found){
Set<String> keys = process.keySet();
Iterator it = keys.iterator();
while(it.hasNext()){
if(process.get((String) it.next()) != 0){
found = false;
break;
}
}
}
if(found) results.add(index);
index++;
}
return results;
}
private HashMap<String, Integer> buildMap(String[] L){
HashMap<String, Integer> process = new HashMap<String, Integer>();
for(String lp : L){
if(process.containsKey(lp)){
process.put(lp, process.get(lp) + 1);
}else{
process.put(lp, 1);
}
}
return process;
}
}
没有评论:
发表评论