今天是紀錄LeetCode解題的第三十天

成功堅持一個月了!剛好今天也是困難題

第三十題題目：
You are given a string s and an array of strings words. All the strings of words are of the same length.

A concatenated string is a string that exactly contains all the strings of any permutation of words concatenated.

• For example, if words = ["ab","cd","ef"], then "abcdef", "abefcd", "cdabef", "cdefab", "efabcd", and "efcdab" are all concatenated strings. "acdbef" is not a concatenated string because it is not the concatenation of any permutation of words.

Return an array of the starting indices of all the concatenated substrings in s. You can return the answer in any order.

給定一個字串s和數組words，所有words裡的字串長度都相同，請找出所有的起始索引，使得從該索引開始的子字串，是words中所有字串的串接（concatenation）

• 例如，如果words = ["ab","cd","ef"]，則"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"和"efcdab"都是連接字串。"acdbef"不是連接字串，因為它不是words的任何排列的連接

傳回所有連接子字串的起始索引數組，可以按任意順序返回答案

解題思路

我們利用滑動視窗的方式，一次擷取words中的字串的長度大小，如果擷取的字串存在於words中，那就計算該字串出現的次數，如果出現的次數大於words中字串的次數，那麼我們就縮小左邊邊界，直到縮減至小於等於我們要找的次數，如果總次數等於words總字串次數，這時候的左邊界left就是我們要找的索引值

程式碼

from collections import Counter

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        word_len = len(words[0])
        word_count = len(words)
        total_len = word_len * word_count
        s_len = len(s)

        if s_len < total_len:
            return []

        target = Counter(words)
        result = []

        for offset in range(word_len):
            left = offset
            right = offset
            window_count = Counter()
            count = 0

            while right + word_len <= s_len:
                word = s[right:right+word_len] #擷取字串
                right += word_len #右移

                if word in target: #如果找到的字串是要找的
                    window_count[word] += 1 #計算該字串次數
                    count += 1 #計算所有字串出現次數

                    while window_count[word] > target[word]:#如果出現的字串次數大於要尋找的字串次數
                        left_word = s[left:left+word_len] #左邊開始收縮
                        window_count[left_word] -= 1
                        left += word_len
                        count -= 1

                    if count == word_count:
                        result.append(left)
                else:
                    window_count.clear()
                    count = 0
                    left = right

        return result

Counter類別

Counter是一種特別的「字典（dict）」，專門用來「統計元素出現次數」

基本用法

from collections import Counter

s = "leetcode"
counter = Counter(s)
print(counter)
#輸出：Counter({'e': 3, 'l': 1, 't': 1, 'c': 1, 'o': 1, 'd': 1})

Counter也可以用在List

from collections import Counter

words = ["foo", "bar", "foo", "bar", "bar"]
c = Counter(words)
print(c)
#輸出：Counter({'bar': 3, 'foo': 2})

執行過程

初始狀態

• s = "wordgoodgoodgoodbestword"
• words = ["word","good","best","word"]
• word_len = 4
• word_count = 4
• total_len = word_len * word_count = 4 * 4 = 16
• s_len = 24
• target = Counter({'word': 2, 'best': 1, 'good': 1})
• result = []

offset = 0

• left = offset = 0
• right = offset = 0
• window_count = Counter({})
• count = 0
• while right + word_len <= s_len → 4 <= 24 → True
• word = s[right:right+word_len] = s[0:4] = "word"
• right += word_len → right = 4
• if word in target → True
• window_count[word] += 1 → window_count = ({'word': 1})
• count += 1 → count = 1
• while window_count[word] > target[word] → False
• count == word_count → False (count = 1 、 word_count = 4)

滑動視窗繼續右移

• while right + word_len <= s_len → 8 <= 24 → True
• word = s[right:right+word_len] = s[4:8] = "good"
• right += word_len → right = 8
• if word in target → True
• window_count[word] += 1 → window_count = ({'word': 1, 'good': 1})
• count += 1 → count = 2
• while window_count[word] > target[word] → False
• count == word_count → False (count = 2 、 word_count = 4)

滑動視窗繼續右移

• while right + word_len <= s_len → 12 <= 24 → True
• word = s[right:right+word_len] = s[8:12] = "good"
• right += word_len → right = 12
• if word in target → True
• window_count[word] += 1 → window_count = ({'word': 1, 'good': 2})
• count += 1 → count = 3

開始收縮左邊界

• while window_count[word] > target[word] → True
• left_word = s[left:left+word_len] = s[0:4] = "word"
• window_count[left_word] -= 1 → window_count = ({'word': 0, 'good': 2})
• left += word_len → left = 4
• count -= 1 → count = 2 (good還是超過要搜尋的次數，左邊界繼續收縮)

繼續收縮左邊界

• left_word = s[left:left+word_len] = s[4:8] = "good"
• window_count[left_word] -= 1 → window_count = ({'word': 0, 'good': 1})
• left += word_len → left = 8
• count -= 1 → count = 1

照這個概念依此類推就能找出答案，以上演示如何模擬滑動視窗不斷向右擷取字串，以及收縮左邊界減少擷取字串的執行過程，這題雖然是hard題，但觀念不會太難