townhouse 朝哪个方向比较好？# Living
c*u
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
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
);
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;
}
}
这道题我是用的brute force，所以有时候超时。请问有更好的算法吗？
我的code有几次通过了，耗时200ms，我看最终结果里有很多几十毫秒的。请问那是怎
样的算法呢？
public class Solution {
public List
ArrayList
HashMap
HashMap
int wordsLen = words.length;
int singleLen = words[0].length();
boolean found;
for(int i=0; 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
);
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;
}
}