ORIGIN

LeetCode 30. Substring with Concatenation of All Words

ACM 1 mins316 words

Problem Description

30. Substring with Concatenation of All Words

Analysis

Because all the words are the same length, we can use hash map to check for substring from index i to index i +word length * words number.

Then we can traverse all the i index.

However, we can use sliding window to reduce creation of hash map.

For each start, there are 3 situations:

  1. the current word is not in the word list, then the whole substring is invalid. so the window will start from the next word.
  2. the current word is in the words list, but it appears more times than in the words list. So in this case we start remove words from window in the front, until the other current word is reached and removed.
  3. the words are all matched, so we removed the first word from the window.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
int wordLen = words[0].length(), wordCnt = words.size();
unordered_map<string,int> baseWords, cmpWords;
vector<int> ans;
for(auto i : words) baseWords[i] ++;
for(int i = 0; i < wordLen; i ++) {
cmpWords.clear();
int cnt = 0, tmpStart = i;
for(int j = i; j < s.length(); j += wordLen) {
string curWord = s.substr(j, wordLen);
// 1. current word not in the list
if(baseWords[curWord] == 0) {
cmpWords.clear();
cnt = 0;
tmpStart = j + wordLen;
} else {
cmpWords[curWord] ++;
cnt ++;
// the word occurrence time is exceeds
if(cmpWords[curWord] > baseWords[curWord]) {
// shrink the window front boundary
while(cnt --) {
string toBeDel = s.substr(tmpStart, wordLen);
cmpWords[toBeDel] --;
tmpStart += wordLen;
if(toBeDel == curWord) {
break;
}
}
}
// the words are all matched, remove the first word
if(cnt == wordCnt) {
ans.push_back(tmpStart);
string firstWord = s.substr(tmpStart, wordLen);
cmpWords[firstWord] --;
cnt --;
tmpStart += wordLen;
}
}
}
}
return ans;
}
};
TOP
COMMENT
  • ABOUT
  • |
o_oyao
  The Jigsaw puzzle is incomplete with even one missing piece. And I want to be the last piece to make the puzzle complete.
Like my post?
Default QR Code
made with ❤️ by o_oyao
©o_oyao 2019-2024

|