问题说明:
给定一个字符串，其中包含以空格(空格)分隔的单词，它需要在线性时间(O(n)，其中n是字符串中的字符数)内构建一个数据结构，如果该字符串中的两个单词具有两个共同字符，则该数据结构可以在恒定时间(O(1))内回答。
关于数据结构应该是什么样的有什么想法吗?
谢谢。
你的问题模棱两可。
- 字的定义是什么?
- 恰好两个字符相同还是至少两个字符相同?
- 如果a)字符串中存在两个有两个共同字符的单词，或者b)您将得到一些单词对，并且需要回答这些单词对是否有两个共同字符?
- 在第3点(b)的情况下，输入的格式是什么?输入的是整个单词还是字符串中单词的下标?
我假设一个单词仅由字母字符(a- za -z)组成，并且您将根据其在输入字符串中的索引获得任意一对单词。
定义数组f使，(f[a],...,f[z]) = (0,...,25)和(f[A],...,f[Z]) = (26,...,51)。
让输入字符串S由单词W[0], W[1], ..., W[n-1]组成。通过F(W) = OR(1 << f[c]) for all characters c in word W
如果我们要找出两个词W1, W2是否(假设至少)有两个字符相同，我们只需要找出B = F(W1) & F(W2)是否至少有两个比特。您可以遍历B的所有位，以查找它是否至少有两个位，这仍然是O(1)，或者您可以检查B && (B & (B-1))是否为真。(说明:B & (B-1)取消B的最低设置位，所以如果它不为零，B必须至少有两个比特)
现在您可以为O(|S|)中的每个单词预先计算F(w)，然后通过比较F的值来输出O(1)中的每个查询。