30. Substring with Concatenation of All Words （又超时了，最后一个case没过）

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) ins that is a concatenation of each word inwords exactly once and without any intervening characters.

For example, given: s: "barfoothefoobarman" words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

C语言，超时，最后一个case没过。

代码：

int wordcmp(char** words,char* word,int wordsSize,int *sub,int *number) { //*sub默认是-1；*number默认是0 int k=0; for(k=0;k<wordsSize;k++) { if(strcmp(words[k],word)==0) { (*number)++; *sub=k; } else { continue; } } if((*number)>0) { return 0; } else { return -1; //不包含word } } /** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */ int* findSubstring(char* s, char** words, int wordsSize, int* returnSize) { int i=0,j=0,k=0; int sub=0; int* ret=(int *)malloc(sizeof(int)); int strLength=strlen(s); int wordLength=strlen(words[0]); int number[strLength]; memset( number, 0, strLength*sizeof(int)); for(i=0;i<=strLength-wordsSize*wordLength;i++) { memset( number, 0, strLength*sizeof(int)); for(j=0;j<wordsSize;j++) { int sub=-1; int num=0; char word[wordLength+1]; strncpy(word,s+i+j*wordLength,wordLength); word[wordLength]='\0'; int res=wordcmp(words,word,wordsSize,&sub,&num); if(res!=0) { break; } else { number[sub]++; } //查找word有多少个 if(number[sub]>num) { break; } } if(j==wordsSize) { ret[sub++]=i; } } *returnSize=sub; return ret; }

JAVA版本的，同一个思路。

代码：

public class Solution { public List<Integer> findSubstring(String s, String[] words) { int i=0,j=0; List<Integer> list=new ArrayList<Integer>(); Map<String,Integer> map=new HashMap<String,Integer>(); Map<String,Integer> tmp=new HashMap<String,Integer>(); int strLength=s.length(); int wordsNum=words.length; int wordLength=words[0].length(); //保存所有的words for( i=0;i<wordsNum;i++) { if(map.containsKey(words[i])) { map.put(words[i], map.get(words[i])+1); } else { map.put(words[i], 1); } } for(i=0;i<=strLength-wordsNum*wordLength;i++) { tmp.clear(); for(j=0;j<wordsNum;j++) { String word=s.substring(i+j*wordLength, i+j*wordLength+wordLength); if(!map.containsKey(word)) { break; } if(tmp.containsKey(word)) { tmp.put(word, tmp.get(word)+1); } else { tmp.put(word, 1); } if(tmp.get(word) > map.get(word)) { break; } } if(j==wordsNum) { list.add(i); } } return list; } }