https://youtu.be/fR0tqhqM7Yg
30. Substring with Concatenation of All Words
給定一個字串 s 和一個字串 words 陣列。所有 words 字串的長度都相同。
連接字串是精確包含任何連接的單字排列的所有字串的字串。
例如，如果words = ["ab","cd","ef"]，
則"abcdef"、"abefcd"、"cdabef"、"cdefab"、"efabcd"和"efcdab"都是連接字串。
"acdbef"不是連接字串，因為它不是任何單字排列的連接。
傳回 s 中所有連接子字串的起始索引的陣列。您可以按任意順序返回答案。
Topic: Hash Table, String, Sliding Window
我快吐血
不愧是HARD 真D難
難點在於兩個解答我有一個是完全看不懂的==
Hash Table到底是三小
我直接暴斃
Sliding Window的解法
因為題目已經確定words裡面的word都一樣長度
所以我們可以直接跳格子的方式去找
就是如果有一個word出現 就記錄起來
如果剛好所有word都出現一次 就紀錄starting pointer到result array
如果超過兩次 那就不符合規定了
代表starting pointer到sliding window之間的substring有多餘的word
就把starting pointer往前移動 直到所有word出現次數都 <= 1
from collections import Counter, defaultdict
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
length = len(words[0])
word_count = Counter(words)
indexes = []
for i in range(length):
start = i
window = defaultdict(int)
words_used = 0
for j in range(i, len(s) - length + 1, length):
word = s[j:j + length]
if word not in word_count:
start = j + length
window = defaultdict(int)
words_used = 0
continue
words_used += 1
window[word] += 1
while window[word] > word_count[word]:
window[s[start:start + length]] -= 1
start += length
words_used -= 1
if words_used == len(words):
indexes.append(start)
return indexes