Description
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].
(order does not matter).
Solution
This is an another window-moving problem that can be solved in linear time (not very exactly), which is similar to Minimum Window Substring.
We keep two pointers left and right and lLen is the length of the word in L.
- Step1: We keep increasing
right += lLenand check if we find a valid Concatenation until we find- CASE1:
rightexceeds the length ofS - CASE2: [Partial Overflow] for some string
strinLwe have spotted more than expected number ofstrinS[left, right+lLen-1] - CASE3: we find
S[right, right+len-1]is not a word inL
- CASE1:
- Step2:
- For CASE1 and CASE2, go to step 3
- For CASE3
- move
left = right+lenandright = right+len
- move
- Step3: We keep increasing
left += lLen, until we find- CASE1: left == right
- CASE2: no Partial OVERFLOW exists in S[left, right+len-1] anymore
- Go back to Step 1, if
rightdoes not reach the end
We have to repeat the above procedure for lLen times by initializing left = right = i, i = 0...lLen-1. As we increase left, right by lLen in each iteration, the total time complexity is still , where is the length of S. Rigorously speaking, we have to extract a substring whose length is lLen in each iteration, thus the time complexity is
Code
Running Time: 968ms
1 class Solution {
2 public:
3 vector<int> findSubstring(string S, vector<string> &L) {
4 vector<int> result;
5 if (!S.size() || !L.size())
6 return result;
7 unordered_map<string, int>expectedCount;
8 for (int i = 0; i < L.size(); ++ i)
9 expectedCount[L[i]] = (expectedCount.find(L[i]) == expectedCount.end())?1:expectedCount[L[i]]+1;
10
11 for (int left_start = 0; left_start < L[0].size(); ++ left_start)
12 subLeft(result, left_start, S, L, expectedCount);
13
14
15 return result;
16 }
17
18 void subLeft(vector<int>&result, int left, string &S, vector<string> &L, unordered_map<string, int> & expectedCount){
19 int nSat = 0;
20 int lLen = L[0].size();
21 unordered_map<string, int>realCount;
22 for (int i = 0 ; i < L.size(); ++ i)
23 realCount[L[i]] = 0;
24
25 int right = left;
26 while(right < S.size()-lLen + 1){
27 string str;
28 // increas pointer right until OVERFLOW.
29 while(right < S.size()-lLen + 1){
30 str = S.substr(right, lLen);
31
32 right += lLen;
33 if (expectedCount.find(str) == expectedCount.end()){ // not a word
34 for (unordered_map<string, int>::iterator it = realCount.begin(); it != realCount.end(); ++ it)
35 it->second = 0;
36 nSat = 0;
37 left = right;
38 }
39 else{ // a legal word
40 realCount[str] += 1;
41 if (realCount[str] > expectedCount[str]) {// overflow
42 nSat--;
43 break;
44 }
45 else if (realCount[str] == expectedCount[str]){
46 nSat ++;
47 if (nSat == realCount.size())
48 result.push_back(left);
49 }
50 }
51 }
52 // increas pointer left until OVERFLOW disappears.
53 while(left < right){
54 str = S.substr(left, lLen);
55 left += lLen;
56
57 realCount[str] -= 1;
58 if (realCount[str] == expectedCount[str]){ // overflow disappears
59 nSat ++;
60 if (nSat == realCount.size())
61 result.push_back(left);
62 break;
63 }
64 else if (realCount[str] == expectedCount[str] - 1)
65 nSat --;
66 };
67 }
68 }
69 };