javascript - 确定一个字符串是否是另一个字符串的子集的时间复杂度

Question

确定一个字符串是否是另一个字符串的子集的 Big-O 是什么？换句话说，一个字符串是否包含另一个字符串的所有字符？

例如A = 'string' B = 'gti'，B是 的子集A。

我的方法是使用所有字符A来创建地图。然后，迭代B以与 Map 进行交叉检查。这种方法的大 O 是O(m + n). 这是我能得到的最好的最坏情况时间复杂度吗？

标签： javascriptalgorithmtime-complexity

Answer 1

除非您可以在不（在最坏的情况下）至少检查每个字符串的每个字符的情况下解决问题，否则您不能做得比 O(m+n) 更好（假设 m & n 是 2 个字符串长度）。