c*****u
发帖数: 867 | 1 https://leetcode.com/problems/substring-with-concatenation-of-all-words/
这道题我是用的brute force，所以有时候超时。请问有更好的算法吗？
我的code有几次通过了，耗时200ms，我看最终结果里有很多几十毫秒的。请问那是怎
样的算法呢？
public class Solution {
public List findSubstring(String s, String[] words) {
ArrayList result = new ArrayList();
HashMap wordMap = new HashMap();
HashMap wordCover = new HashMap();
int wordsLen = words.length;
int singleLen = words[0].length();
boolean found;
for(int i=0; i
if(!wordMap.containsKey(words[i])) {
wordMap.put(words[i], 1);
} else {
wordMap.put(words[i], wordMap.get(words[i]) + 1);
}
}
for(int i=0; i<=s.length() - wordsLen * singleLen; i++) {
found = true;
wordCover.clear();
for(int j=0; j
String single = s.substring(i+j*singleLen, i+(j+1)*singleLen
);
if(!wordMap.containsKey(single)) {
found = false;
break;
}
if(!wordCover.containsKey(single)) {
wordCover.put(single, 1);
} else {
wordCover.put(single, wordCover.get(single) + 1);
}
if(wordCover.get(single) > wordMap.get(single)) {
found = false;
break;
}
}
if(found) {
result.add(i);
}
}
return result;
}
} |
|
