f*******w 发帖数: 1243 | 1 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"]
You should return the indices: [0,9].
我的code如下
之前用unordered_set, 如果L里面有重复元素就跑不过
现在改用multiset, 直接出错……
求助求助……
class Solution {
public:
vector findSubstring(string S, vector &L) {
unordered_multiset strset, tmpset;
int numstr = L.size(), strlen = L[0].size();
vector ret;
for(int i = 0; i < numstr; ++i) strset.insert(L[i]);
for(int i = 0; i < (int)S.size() - numstr*strlen + 1; ++i) {
for(int j = 0; j < numstr; ++j) {
string sub = "";
for(int k = 0; k < strlen; ++k)
sub += S[i + j*strlen + k];
auto rit = strset.equal_range(sub);
for(auto it = rit.first; it != rit.second; ++it) {
strset.erase(it);
tmpset.insert(sub);
}
if(rit.first == strset.end()) break;
if(strset.empty()) ret.push_back(i);
}
for(auto it = tmpset.begin(); it != tmpset.end(); ++it)
strset.insert(*it);
tmpset.clear();
}
return ret;
}
}; | j******2 发帖数: 362 | 2 你不能用一个unordered_map来记录下每个词要几次吗? | G****A 发帖数: 4160 | 3 大伙讨论一下解题思路吧。
same
【在 f*******w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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"] : You should return the indices: [0,9]. : 我的code如下
| e******o 发帖数: 757 | 4 正解
【在 j******2 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你不能用一个unordered_map来记录下每个词要几次吗?
| f*******w 发帖数: 1243 | 5 现在能过小case了,大的跑不过去……
class Solution {
public:
vector findSubstring(string S, vector &L) {
unordered_map strset, tmpset;
int numstr = L.size(), strlen = L[0].size();
vector ret;
for(int i = 0; i < numstr; ++i) {
auto it = strset.find(L[i]);
if(it != strset.end()) ++it->second;
else strset.insert(make_pair(L[i], 1));
}
tmpset = strset;
for(int i = 0; i < (int)S.size() - numstr*strlen + 1; ++i) {
for(int j = 0; j < numstr; ++j) {
string sub = "";
for(int k = 0; k < strlen; ++k)
sub += S[i + j*strlen + k];
auto it = strset.find(sub);
if(it == strset.end()) break;
else if(--it->second == 0) strset.erase(it);
}
if(strset.empty()) ret.push_back(i);
strset = tmpset;
}
return ret;
}
}; | f*******w 发帖数: 1243 | 6 string sub = "";
for(int k = 0; k < strlen; ++k)
sub += S[i + j*strlen + k];
改成 string sub = S.substr(i+j*strlen, strlen) 就过large judge了,不过要
1600ms……显然不是什么好解法- - | c********t 发帖数: 5706 | 7 全忘了,做了一下,难。
提示你一下, S="acdcba" L="a","b","c","d"
当发现acdc不match的时候,(因为两个c), index应该直接跳到d来继续search, 而不
能index++
【在 f*******w 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 现在能过小case了,大的跑不过去…… : class Solution { : public: : vector findSubstring(string S, vector &L) { : unordered_map strset, tmpset; : int numstr = L.size(), strlen = L[0].size(); : vector ret; : for(int i = 0; i < numstr; ++i) { : auto it = strset.find(L[i]); : if(it != strset.end()) ++it->second;
|
|