e***s
发帖数: 799 | 1 在LEETCODE OJ 的一题
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"]
下面是我的代码，在small case 4ms 通过， big case Time Limit Exceeded，不知道
为什么，求解答。
vector findSubstring(string S, vector &L) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector ret;
map map_count;
map map_found;
int l = L[0].length();
int total = L.size();
for (int i = 0; i < total; i++)
{
if (map_count.find(L[i]) != map_count.end())
map_count[L[i]]++;
else
map_count.insert(pair(L[i], 1));
}
int leastlength = S.length() - l * total;
for (int i = 0; i <= leastlength ; i++)
{
int index = i;
while (total > 0)
{
string sub = S.substr(index, l);
if (map_count.find(sub) == map_count.end())
break;
else if (map_found.find(sub) != map_found.end() && map_found
[sub] >= map_count[sub])
break;
else
{
if (map_found.find(sub) != map_found.end())
map_found[sub]++;
else
map_found.insert(pair(sub, 1));
total--;
index += l;
}
}
if(total == 0)
ret.push_back(i);
total = L.size();
map_found.clear();
}
return ret;
} |
|
