搜索此博客

2012年9月9日星期日

Substring with Concatenation of All Words


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"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;
}

没有评论:

发表评论