4

让我们考虑 n 个单词，每个单词的长度为 k。这些单词由具有定义顺序的字母表（其基数为 n）组成。任务是推导出一个 O(nk) 算法来计算相差一个位置的单词对的数量（不管是哪一个，只要它只是一个位置）。

例如，在以下一组单词中（n = 5，k = 4）：

abcd、abdd、adcb、adcd、aecd

有 5 个这样的对：（abcd，abdd），（abcd，adcd），（abcd，aecd），（adcb，adcd），（adcd，aecd）。

到目前为止，我已经设法找到一种算法来解决一个稍微简单的问题：计算相差一个 GIVEN 位置（第 i 个）的单词对的数量。为了做到这一点，我将第 i 个位置的字母与每个单词中的最后一个字母交换，执行基数排序（忽略每个单词中的最后一个位置 - 以前是第 i 个位置），线性检测字母在第一个 1 到k-1 个位置相同，最终计算每个字母在每组重复项中最后（最初是第 i 个）位置的出现次数，并计算所需的对（最后一部分很简单）。

然而，上面的算法似乎不适用于主要问题（在 O(nk) 约束下）——至少在没有一些修改的情况下不能。知道如何解决这个问题吗？

4

5 回答 5

1

假设 n 和 k 不是太大，这样这将适合内存：

有一个删除第一个字母的集合，一个删除第二个字母的集合，一个删除第三个字母的集合，等等。从技术上讲，这必须是从字符串到计数的映射。

遍历列表，只需将当前元素添加到每个映射（显然首先删除适用的字母）（如果它已经存在，将计数添加到 totalPairs 并将其加一）。

然后 totalPairs 是所需的值。

编辑：

复杂：

这应该是O(n.k.logn)。

您可以使用使用散列的映射（例如HashMap在 Java 中），而不是排序映射，以实现理论上的复杂性O(nk)（尽管我通常发现哈希映射比基于树的排序映射要慢）。

改进：

对此的一个小改动是将前 2 个字母的映射删除为 2 个映射，一个删除第一个字母，一个删除第二个字母，第三个和第四个字母相同，依此类推。

然后将它们放入删除了 4 个字母的地图中，将这些放入删除了 8 个字母的地图中，依此类推，最多删除一半的字母。

其复杂性在于：

  • 您对包含最大 k 个元素（每半个）的 2 个排序集进行 2 次查找。

  • 对于其中的每一个，您再次对 2 个排序集进行 2 次查找（对于每个季度）。

  • 所以查找次数是 2 + 4 + 8 + ... + k/2 + k，我相信是O(k).

  • 我在这里可能是错的，但是，最坏的情况是，任何给定地图中的元素数量是n，但这将导致所有其他地图只有 1 个元素，所以仍然是O(logn)，但是对于每个n（不是每个n.k）。

所以我认为是O(n.(logn + k))。

.

编辑2：

我的地图示例（没有改进）：

(x-1)表示x映射到1。

假设我们有abcd, abdd, adcb, adcd, aecd.

第一张地图是(bcd-1), (bdd-1), (dcb-1), (dcd-1), (ecd-1).

第二张地图将是(acd-3), (add-1), (acb-1)（对于第 4 和第 5，值已经存在，因此增加）。

第三张地图：（(abd-2), (adb-1), (add-1), (aed-1)第二张已经存在）。

第四张地图：（(abc-1), (abd-1), (adc-2), (aec-1)第四张已经存在）。

totalPairs = 0

对于第二张地图 - acd，对于第四张，我们加 1，对于第五张我们加 2。

totalPairs = 3

对于第三张地图 - abd，对于第二张，我们加 1。

totalPairs = 4

对于第四张地图 - adc，对于第四张，我们加 1。

totalPairs = 5.

改进地图的部分示例：

与上述相同的输入。

删除前 2 个字母的映射到删除第 1 个和第 2 个字母的映射：

(cd-{  {(bcd-1)}, {(acd-1)}  }),
(dd-{  {(bdd-1)}, {(add-1)}  }),
(cb-{  {(dcb-1)}, {(acb-1)}  }),
(cd-{  {(dcd-1)}, {(acd-1)}  }),
(cd-{  {(ecd-1)}, {(acd-1)}  })

上面是一个由cd映射到 2 个映射的元素组成的映射，一个包含一个元素(bcd-1)，另一个包含(acd-1).

但是因为第 4 和第 5cd已经存在，所以，不是生成上面的，而是将其添加到该地图中，如下所示：

(cd-{  {(bcd-1, dcd-1, ecd-1)}, {(acd-3)}  }),
(dd-{  {(bdd-1)}, {(add-1)}  }),
(cb-{  {(dcb-1)}, {(acb-1)}  })
于 2013-01-04T20:15:04.393 回答
0

您可以将每个单词放入一个数组中。从该数组中逐个弹出元素。然后比较结果数组。最后将弹出的元素添加回原始数组。两个数组中弹出的元素不能相同。计算发生这种情况的情况，最后除以 2 得到准确的解决方案

于 2012-11-07T04:57:17.207 回答
0

我在这里提交问题已经两个月了。在此期间，我已与同行讨论过，并希望分享结果。

主要思想类似于杜克林提出的思想。对于每个单词 A 和该单词中的每个第 i 个位置，我们将考虑一个元组：（前缀、后缀、第 i 个位置的字母），即 (A[1..i-1], A[i+1. .n]，A[i])。如果 i 是 1 或 n，则适用的子字符串被认为是空的（这些是简单的边界情况）。

有了这些元组，我们应该能够应用我在第一篇文章中提供的推理来计算不同单词对的数量。我们所要做的就是按前缀和后缀值对元组进行排序（对每个 i 分别） - 然后，字母完全相等但第 i 个位置的单词将彼此相邻。

这是我缺乏的技术部分。为了使排序过程（RadixSort 似乎是要走的路）满足 O(nk) 约束，我们可能想要为我们的前缀和后缀分配标签（每个 i 只需要 n 个标签）。我不太清楚如何处理标签的事情。（当然，我们可能会做一些散列，但我非常有信心前一种解决方案是可行的）。

虽然这不是一个完全完整的解决方案，但我相信它为解决这个问题的可能方法提供了一些启示，这就是我在这里发布它的原因。如果有人想出如何做标签部分的想法，我将在这篇文章中实现它。

于 2013-01-11T19:59:24.253 回答
0

想想你将如何枚举语言——你可能会使用递归算法。递归算法映射到树结构。如果你构建这样一棵树，每个分歧代表一个字母的差异，每个叶子代表语言中的一个单词。

于 2013-01-05T19:40:50.917 回答
0

以下 Python 解决方案如何？

import string

def one_apart(words, word):
    res = set()
    for i, _ in enumerate(word):
        for c in string.ascii_lowercase:
            w = word[:i] + c + word[i+1:]
            if w != word and w in words:
                res.add(w)
    return res


pairs = set()
for w in words:
  for other in one_apart(words, w):
    pairs.add(frozenset((w, other)))

for pair in pairs:
  print(pair)

输出：

frozenset({'abcd', 'adcd'})
frozenset({'aecd', 'adcd'})
frozenset({'adcb', 'adcd'})
frozenset({'abcd', 'aecd'})
frozenset({'abcd', 'abdd'})
于 2020-08-22T04:20:47.250 回答