1import math
2from collections import namedtuple
3class Solution:
4 def smallestSubarrayCoveringSet(self, paragraph, keywords):
5 subarray = namedtuple("subarray", ("start", "end"))
6 keywordToIndex = {k: i for i, k in enumerate(keywords)}
7 latestOccurence = [-1 for _ in range(len(keywords))]
8 shortestSubarrayLength = [math.inf for _ in range(len(keywords))]
9 shortestDistance = math.inf
10 result = subarray(-1, -1)
11
12 for i, p in enumerate(paragraph):
13 if p in keywordToIndex:
14 keywordIndex = keywordToIndex[p]
15 if keywordIndex == 0: shortestSubarrayLength[keywordIndex] = 1
16 elif shortestSubarrayLength[keywordIndex - 1] != math.inf:
17 distanceToPreviousKeyword = (i - latestOccurence[keywordIndex - 1])
18 shortestSubarrayLength[keywordIndex] = (distanceToPreviousKeyword + shortestSubarrayLength[keywordIndex - 1])
19 latestOccurence[keywordIndex] = i
20
21 if (keywordIndex == len(keywords) - 1 and shortestSubarrayLength[-1] < shortestDistance):
22 shortestDistance = shortestSubarrayLength[-1]
23 result = subarray(i - shortestDistance + 1, i)
24
25 return result