runtime 93 ms, beats 86.55% of cpp submissions
O(a+nb) solution with explanation

tags: sliding window, hash table

Substring with Concatenation of All Words

📖 description

給定一個句子 s ，與一組 words 含有需要組合的字串，回傳有多少子字串可以完美被 words 組合 (開頭)。
其中 words 裡的每個單字都是等長的

ex.
    s = "barfoothefoobarman", words = ["foo","bar"]

    符合條件的子字串有
        - 開頭 0 : barfoo
        - 開頭 9 : foobar

🧠 solution

從題目中大概可以發現這是個不同版本的 sliding window 類型的題目，只是將元素從字元或數字換成字串。
所以本題的重點不在於如何實作 sliding window ，而在於該如何從基礎加速，有以下幾點要注意。

  • 本題並不像正常的題目一樣只需要對 s 做一次 sliding window ，根據 words 內單字長度 (b) 的不同，我們要對前 b 個字元做一次操作，這是因為我們必須讓 window 涵蓋所有範圍。
  • 在做 sliding window 的時候，如果看到不在 words 的單字，可以直接移動指標，並把狀態重製，來減少操作。
ex.
    s = "bbarfooobarfoo", words = [bar,foo]
    因為單字的長度為 3 ，我們要針對 s 的 [0,1,2] 開頭

    0 : [bba, rfo, oob, arf] 沒有符合
    1 : [bar, foo, oba, rfo] 有符合 (1)
    2 : [arf, ooo, bar, foo] 有符合 (8)

    所以答案是 [1, 8]

⏳ time complexity

a 表示 words 的長度， b 表示 words 內單字的長度， n 表示 s 的長度
建構 hash table 需要花 O(a) ，針對前 b 個字元做一次 sliding window 時間複雜度 O(nb)
總時間複雜度 O(a+nb)

📝 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
47
48
49
50
51
52
53
54
55
56
class Solution {
public:
    void slide(int left,vector<string>& words,string& s,unordered_map<string,int>& map,vector<int>& ans){
        unordered_map<string,int> seen;
        vector<string> tok;
        int wss = words.size();
        int ws = words[0].size();
        int cnt = 0,l = 0,r = 0;
        bool flag = false;      // 有沒有看到超過的單字
        for(int i=left;i<s.size();i+=ws){   // 把 s 切成 token
            string tmp = s.substr(i,ws);
            tok.emplace_back(tmp);
        }
        while(r<tok.size() && l<tok.size()){
            if(flag==false && cnt<words.size()){
                seen[tok[r]]++;
                if(map.find(tok[r])==map.end()){    // 如果當前單字沒有在 words 裡，重製狀態
                    seen.clear();
                    l = r+1;
                    cnt=-1;         // -1 是因為後面會加一，要歸零
                }
                else if(seen[tok[r]]>map[tok[r]]){
                    flag = true;    // 有看到超過的單字
                }
                else{
                    if(cnt==wss-1){
                        ans.emplace_back(left+ws*l);    // 當前答案
                    }
                }
                cnt++;
                r++;
            }
            else{
                while((flag==true || cnt>=wss)){    // 如果有條件不滿足，調整 l 讓條件滿足為止
                    if(seen[tok[l]]>map[tok[l]]){
                        flag = false;
                    }
                    seen[tok[l]]--;
                    l++;
                    cnt--;
                }
            }
        }
    }
    vector<int> findSubstring(string& s, vector<string>& words) {
        unordered_map<string,int> map;
        vector<int> ans;
        for(int i=0;i<words.size();i++){
            map[words[i]]++;            // 建立 hash table
        }
        for(int i=0;i<words[0].size();i++){
            slide(i,words,s,map,ans);   // sliding window
        }
        return ans;
    }
};