# 30. Substring with Concatenation of All Words

----------------------------------------------------------------------------

Mean:

analyse:

Trick:集合words是一个可重集，当连续出现的单词书大于words中的时，需要回退删除开头部分的单词，注意细节.

Time complexity: O(N)

view code

class Solution
{
public :

vector < int > findSubstring( string s , vector < string > & words)
{
vector < int > ans;
int n = s . size (), cnt = words . size();
if (n <= 0 || cnt <= 0) return ans;

// init word occurence
unordered_map < string , int > dict;
for ( int i = 0; i < cnt; ++ i)   //统计每个单词出现的次数
dict [ words [ i ]] ++;

// travel all sub string combinations
int wl = words [ 0 ]. size();
for ( int i = 0; i < wl; ++ i)
{
int left = i , continueWords = 0;
unordered_map < string , int > tdict;
for ( int j = i; j <= n - wl; j += wl)
{
string str = s . substr( j , wl);
// a valid word, accumulate results
if ( dict . count( str))
{
tdict [ str ] ++;
if ( tdict [ str ] <= dict [ str ])
continueWords ++;
else
{
// a more word, advance the window left side possiablly
while ( tdict [ str ] > dict [ str ])
{
string str1 = s . substr( left , wl);
tdict [ str1 ] --;
if ( tdict [ str1 ] < dict [ str1 ]) continueWords --;
left += wl;
}
}

// come to a result
if ( continueWords == cnt)
{
ans . push_back( left);
tdict [s . substr( left , wl )] --;
continueWords --;
left += wl;
}
}
// not a valid word, reset all vars
else
{
tdict . clear();
continueWords = 0;
left = j + wl;
}
}
}
return ans;
}
};

LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
LeetCode contest 187 1437. 是否所有 1 都至少相隔 k 个元素 Check If All 1's Are at Least Length K Places Away
92 0
|
iOS开发
LeetCode All in One 题目讲解汇总(持续更新中...)

4164 0
[LeetCode] Substring with Concatenation of All Words
I think the following code is self-explanatory enough. We use an unordered_map counts to record the expected times of each word and another unordered_map seento record the times we have seen.
830 0
|
10天前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
18 2