| 题目链接 | 30. 串联所有单词的子串 |
|---|---|
| 思路 | 滑动窗口 |
| 题解链接 | 官方题解 |
| 关键点 | 线性平移的动作；有明确状态量；应当使用滑动窗口 |
| 时间复杂度 | \(O(\text{len}(\text{words}_0))\times\text{len}(s))\) |
| 空间复杂度 | \(O(\text{len}(\text{words}_0)\times\#\text{words})\) |
代码实现：
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
answer = []
m = len(words)
n = len(words[0])
ls = len(s)
for i in range(n):
if i + m * n > ls:
break
diff = defaultdict(int)
for j in range(m):
word = s[i + j * n : i + (j+1) * n]
diff[word] += 1
for word in words:
diff[word] -= 1
if diff[word] == 0:
del diff[word]
for start in range(i, ls-m*n+1, n):
if start != i:
word = s[start + (m-1)*n: start + m*n]
diff[word] += 1
if diff[word] == 0:
del diff[word]
word = s[start - n: start]
diff[word] -= 1
if diff[word] == 0:
del diff[word]
if len(diff) == 0:
answer.append(start)
return answer