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"]
public ArrayList<Integer> findSubstring(String S, String[] L) {
ArrayList<Integer> result=new ArrayList<Integer>();
Hashtable<String,Integer>ht=new Hashtable<String,Integer>();
for(int i=0;i<L.length;i++)
{
if(!ht.containsKey(L[i]))
{
ht.put(L[i],1);
}
}
int len=L[0].length();
int totalLen=L.length*len;
int start=0;
while(start+totalLen<=S.length())
{
String tempStr=S.substring(start,start+totalLen);
String starter=tempStr.substring(0,len);
if(!ht.containsKey(starter))
{
start++;
continue;
}
String[] strs=new String[L.length];
ArrayList<String>show=new ArrayList<String>();
for(int i=0;i+len<=totalLen;i=i+len)
{
strs[i/len]=tempStr.substring(i,i+len);
show.add(strs[i/len]);
}
for(int j=0;j<L.length;j++)
{
if(show.contains(L[j]))
show.remove(L[j]);
else
break;
}
if(show.isEmpty())
{
result.add(start);
start=start+len;
}
else
{
start++;
}
}
return result;
}
ArrayList<Integer> result=new ArrayList<Integer>();
Hashtable<String,Integer>ht=new Hashtable<String,Integer>();
for(int i=0;i<L.length;i++)
{
if(!ht.containsKey(L[i]))
{
ht.put(L[i],1);
}
}
int len=L[0].length();
int totalLen=L.length*len;
int start=0;
while(start+totalLen<=S.length())
{
String tempStr=S.substring(start,start+totalLen);
String starter=tempStr.substring(0,len);
if(!ht.containsKey(starter))
{
start++;
continue;
}
String[] strs=new String[L.length];
ArrayList<String>show=new ArrayList<String>();
for(int i=0;i+len<=totalLen;i=i+len)
{
strs[i/len]=tempStr.substring(i,i+len);
show.add(strs[i/len]);
}
for(int j=0;j<L.length;j++)
{
if(show.contains(L[j]))
show.remove(L[j]);
else
break;
}
if(show.isEmpty())
{
result.add(start);
start=start+len;
}
else
{
start++;
}
}
return result;
}
没有评论:
发表评论