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