1 題目描述


會提供words跟s，要求找出s中所有words的連續子串的起始索引。

2 解法

2.1 一個個慢慢找

  • 我們從i=0開始檢查，取s[i:i+word_len]叫做word（圖片橘色部分）
  • 有一個word_dic負責紀錄要求，也就是words中的word的數量
  • 有一個seen負責紀錄已經看過且是word_dic的word，可以用來與word_dic比較判斷當前的window是否滿足狀況

擴展window的條件：

  • 基本上擴展window的時機點是透過count的移動來移動window，但是何時要移動count呢？
  • 當前的word是合法的條件？
    1. 當前的word是word_dic中的word
    2. 當前的seen[word]小於word_dic[word]
  • word 合法之後要做哪些工作？
    1. count要+1，count用來計算start的位置以及判斷是否滿足word_dic的數量要求

紀錄i的時機

  • 當我們發現滿足count等於len(words)時，代表我們找到了一個合法的window，這時候要紀錄i的位置
    • 因為count只會在word合法的時候+1，所以當count等於len(words)時，代表我們找到了一個合法的window，這時候要紀錄start的位置

停止當前window的條件是：

  • 何時檢查要停下來？
    1. 如果word不在word_dic中，或者seen[word]大於word_dic[word]，就要停下來，換下一個i開始檢查
      • 舉例來說foofoobar可以組成seen={foo:2, bar:1}，但是我們要的是word_dic={foo:1, bar:1}
      • foo的數量已經超過了，所以當前的window不合法，也就是i是不合法的，我們要往下一個開始檢查。
  • 停下來後要做哪些事情？
    1. count要歸零，seen要清空，重新來過
    2. i要+1，開始下一個window的檢查
  • i要檢查到哪裡？
    • i要檢查到s的長度減去word_len * words_count
    • 因為如果i到len(s)-word_len * words_count這裡都沒有找到合法的window，那麼後面的window也不可能找到合法的window，因為後面的長度已經不夠湊出words的長度了
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
"""
Time: O(n*k)
- n is the length of s
- k is the counts of words, len(words)
Space: O(n)
- n for seen
"""
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        word_dic = defaultdict(int)
        word_len, words_count = len(words[0]), len(words)
        res = []
        # 紀錄words中的word數量
        for word in words:
            word_dic[word] += 1
        # 一個個判斷當前的i是否可以湊出words
        for i in range(len(s) - word_len * wor)
            # 換下一個i開始檢查，count要歸零，seen要清空
            count = 0
            seen = defaultdict(int)
            # 如果 count (當前滿足的數量) 仍然小於 words_count (words的數量) 那就繼續做直到 非法跳出 或是 count數量湊足了
            while count < words_count:
                word = s[i+count*word_len:i+(count+1)*word_len]
                seen[word] += 1
                # 合法：如果數量小於等於word_dict[word]，就可以繼續
                if word in word_dict and seen[word] <= word_dict[word]: 
                    count += 1        
                # 不合法：如果數量超過也不合法
                else:
                    break
            # 如果count等於words_count，代表我們找到了一個合法的window
            if count == words_count:
                res.append(i)
        return res

2.2 跳躍式尋找


我們發現每次檢查的時候都是以word_len為單位去尋找，如果word_len=3我們是不是就可以歸類出以上情況。

以i=0為單位去檢查

  • 從上圖可以發現，以三個三個為單位，如果發現滿足，就透過j移動到下一個word
  • 如果發現當前的word不在word_dic裡面，表示這個start肯定不合格
    • 所以我們要移動start到下一個word的位置
    • 清空seen, count重新開始

  • 如果發現相同word的數量太多時，我們可以透過縮window移除重複的word
    • 因為移除window的word，所以移動start到下一個位置
    • 減少count的數量
    • 減少seen[first_word_in_window]的數量
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
"""
Time: O(n*k)
- n is the length of s (儘管是跳躍式檢查，基本上每個char都會被檢查一次)
- k is the counts of words, len(words) (因為有while迴圈，最壞的狀況是 [b,b,b,b,a,a] 假設 a 只要 1 個，就要先把前面所有的b都移除，所以這個while會執行len(words)次)
Space: O(n)
"""
class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []
        word_dic = defaultdict(int)
        word_len, words_count = len(words[0]), len(words)
        res = []
        # 紀錄words中的word數量
        for word in words:
            word_dic[word] += 1

        # 以word_len為單位去檢查
        for i in range(word_len):
            count = 0 
            seen = defaultdict(int)
            # 因為我們 i 不像之前從 0~n-word_len*words_count，所以我們需要一個start來協助我們記住起點
            start = i
            # 從 i 開始每次跳 word_len 去檢查
            for j in range(i, len(s) - word_len + 1, word_len):
                word = s[j:j+word_len]
                if word in word_dic:
                    count += 1
                    seen[word] += 1
                    # 如果加了當前的word導致數量超過了，移動當前的window，把第一個word移除
                    while seen[word] > word_dic[word]:
                        first_word = s[start:start+word_len]
                        seen[first_word] -= 1
                        left += word_len
                        count -= 1
                    # 如果count等於words_count，代表我們找到了一個合法的window
                    if count == words_count: 
                        res.append(start)
                else:
                    seen = defaultdict(int)
                    count = 0
                    start = j + word_len
        return res

3 結論

這題我真的想了很久…真的有Hard的程度，最一開始能想到的是從i開始慢慢往下移動去檢查的，但是會TLE，後來看了解答才知道可以跳躍式的去檢查，這樣就可以避免TLE了。

參考資料