algorithm - 确定给定字符集是否覆盖给定单词集的算法

Question

我遇到了以下算法问题（src：http ://www.careercup.com/question?id=15029889 ）

问题：c = 'a'<br> w = “apple”<br> c 覆盖 w，当且仅当 w 包含 c。
c_set = {'a', 'b', 'c', 'g'}
w_set = {'apple', 'ibm', 'cisco', 'google'}
c_set 覆盖 w_set，如果 w_set 中的每个 w 都被覆盖c_set 中的一些 c。
给定c_set和w_set，w_set是否被c_set覆盖？
跟进：如果 w_set 是固定的，比如说一本书，如何判断一个 c_set 是否覆盖了这个 w_set？

一种可能的解决方案是：
如果我们使用 26 位（每个字符 1 位）来表示 w_set 中的每个单词，
然后还为 c_set 形成类似的位掩码，则检查覆盖率的解决方案
是执行“c_set_bitmask & word_i_bitmask”。如果这对于每个单词都是非零的
，那么我们已经覆盖了每个单词。

我的问题是，鉴于w_set 是静态的，例如一本书 ，我们能做比这更好的事情吗？

Answer 1

一种可能的解决方案是 O(nlogk) ~ O(n)，其中 n = w_set 中的“字母”总数，k = c_set 中的字母数。max(k) = 26。因此我们可以假设 k 是常数。

该算法看起来很幼稚，但我看不出比 O(n) 更好的解决方案，因为在任何算法中，您至少需要扫描 w_set 中的所有字母以检查它们是否存在于 c_set 中。

按字典顺序对 c_set 进行排序。(O(klogk)) ~ constant
扫描 w 中的每个单词并对 c_set 中的字母进行二分查找。(O(nlogk)) ~ O(n)。