检查一个集合是否包含在另一个集合中的时间复杂度

Question

我正在尝试实现查找包含模式 char 的给定字符串 s 的最短子字符串的示例。我的代码运行良好，但我的目标是达到 O(N) 的时间复杂度，其中 N 是 s 的长度。 这是我的代码；

def shortest_subtstring(s,char):
#smallest substring containing char.use sliding window
start=0
d=defaultdict(int)
minimum=9999
for i in range(len(s)):
    d[s[i]]+=1
    #check whether all the characters from char has been visited.
    while set(char).issubset(set([j for j in d if d[j]>0])):
        #if yes, can we make it shorter

        length=i-start+1
        minimum=min(length,minimum)
        if length==minimum:
            s1=s[start:i+1]
        d[s[start]]-=1
        start+=1
return (minimum,s1)

我的问题在线;

 while set(char).issubset(set([j for j in d if d[j]>0]))

每次我检查char的所有字符串是否都保存在我的字典中，使用is.subset的想法。我可以知道如何在我的代码中找到这一步的时间复杂度吗？是 O(1) 吗，这对于检查一个元素是否存在于集合中是正确的。否则时间复杂度会比O(N)大很多。感谢帮助。

Answer 1

Per docs s.issubset(t) 等同于 s <= t 意味着在操作期间它将测试 s 中的每个元素是否在 t 中。

最佳场景： 如果 s 是 t 的第一个元素 -> O(1)

最坏情况： 如果 s 在 t 的最后一个元素中 -> O(len(t))

那是针对 isubset 的。对于列表理解：

j for j in d 是获取每个键的 O(n)

if d[j]>0 是 O(n) 用于比较字典的每个值 d

Here您可以找到更多信息。