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 的大作中提到】
: 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 的大作中提到】
: 你不能用一个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 的大作中提到】
: 现在能过小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;
|
|
