[LeetCode解題攻略] 30. Substring with Concatenation of All Word

題目描述

給定一個字符串 s 和一個由多個單詞組成的列表 words，請找出所有能夠在字符串 s 中連續拼接所有單詞的子字符串的起始索引。

• 每個單詞的長度相同。
• 所有單詞可以以任意順序連接。

範例 1:

Input: s = "barfoothefoobarman", words = ["foo", "bar"]
Output: [0,9]
Explanation: 子串 "barfoo" 和 "foobar" 均包含 words 中的所有單詞。

範例 2:

Input: s = "wordgoodgoodgoodbestword", words = ["word", "good", "best", "word"]
Output: []
Explanation: 無法找到包含所有單詞的子串。

範例 3:

Input: s = "barfoofoobarthefoobarman", words = ["bar", "foo", "the"]
Output: [6,9,12]

解法一：暴力法

思路

1. 計算 words 的總長度 total_len，每個單詞的長度為 word_len。
2. 遍歷字符串 s，以每個起始位置檢查長度為 total_len 的子串是否包含所有單詞。
3. 使用計數器檢查子串中的單詞分佈是否與 words 一致。

程式碼實現

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        total_len = word_len * len(words)
        word_count = Counter(words)
        n = len(s)

        result = []

        for i in range(n - total_len + 1):
            substring = s[i:i + total_len]
            seen = Counter([substring[j:j + word_len] for j in range(0, total_len, word_len)])
            if seen == word_count:
                result.append(i)

        return result

時間與空間複雜度

• 時間複雜度: O(n * k)，其中 n 是字符串長度、 k 是單詞的數量。
• 空間複雜度: O(k)，其中 k 是單詞的數量。

解法二：滑動窗口法

思路

1. 使用滑動窗口逐步檢查子串是否符合條件。
2. 每次移動窗口時，只檢查新加入的單詞，減少重複計算。

程式碼實現

class Solution:
    def findSubstring(self, s: str, words: List[str]) -> List[int]:
        if not s or not words:
            return []

        word_len = len(words[0])
        total_len = word_len * len(words)
        word_count = Counter(words)
        n = len(s)

        result = []

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

            while right + word_len <= n:
                word = s[right:right + word_len]
                right += word_len

                if word in word_count:
                    window_count[word] += 1
                    count += 1

                    while window_count[word] > word_count[word]:
                        left_word = s[left:left + word_len]
                        window_count[left_word] -= 1
                        count -= 1
                        left += word_len

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

        return result

時間與空間複雜度

• 時間複雜度: O(n * word_len)，因為滑動窗口法只需遍歷一次字符串。
• 空間複雜度: O(k)，其中 k 是單詞的數量。

總結

1. 暴力法適合小規模輸入，但在實際應用中效率較低。
2. 滑動窗口法利用窗口特性有效地減少重複計算，是解決此問題的最佳方案。

選擇解法時需考慮輸入規模和時間性能需求。