題目描述
給定一個字符串 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]
解法一：暴力法
思路
- 計算
words的總長度total_len，每個單詞的長度為word_len。 - 遍歷字符串
s，以每個起始位置檢查長度為total_len的子串是否包含所有單詞。 - 使用計數器檢查子串中的單詞分佈是否與
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 是單詞的數量。
解法二：滑動窗口法
思路
- 使用滑動窗口逐步檢查子串是否符合條件。
- 每次移動窗口時，只檢查新加入的單詞，減少重複計算。
程式碼實現
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 是單詞的數量。
總結
- 暴力法適合小規模輸入，但在實際應用中效率較低。
- 滑動窗口法利用窗口特性有效地減少重複計算，是解決此問題的最佳方案。
選擇解法時需考慮輸入規模和時間性能需求。
