You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.
For example, given:
S:
L:
S:
"barfoothefoobarman"
L:
["foo", "bar"]
You should return the indices:
(order does not matter).
[0,9]
.(order does not matter).
Solution:
public ArrayList<Integer> findSubstring(String S, String[] L) {
HashMap<String, Integer> Lmap = new HashMap<String, Integer>();
HashMap<String, Integer> Smap = new HashMap<String, Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
int total = L.length;
if(total==0)
return result;
for(int i=0;i<total;i++)
{
if(!Lmap.containsKey(L[i]))
Lmap.put(L[i], 1);
else
{
int k = Lmap.get(L[i]);
Lmap.put(L[i], k+1);
}
}
int len = L[0].length();
for(int i=0;i<=S.length()-len*total;i++)
{
Smap.clear();
int j = 0;
for(;j<total;j++)
{
String s = S.substring(i+j*len, i+(j+1)*len);
if(!Lmap.containsKey(s))
break;
if(!Smap.containsKey(s))
Smap.put(s, 1);
else
{
int k = Smap.get(s);
Smap.put(s, k+1);
}
if(Smap.get(s)>Lmap.get(s))
break;
}
if(j==total)
{
result.add(i);
}
}
return result;
}
No comments:
Post a Comment