string - 谷歌采访 : Find Crazy Distance Between Strings

Question

这个问题是在谷歌面试时问我的。我可以做到 O(n*n) ... 我能在更好的时间做到吗？ 一个字符串只能由 1 和 0 组成。

定义:

X & Y 是由 0 或 1 组成的字符串

D(X,Y) = 从 X 和 Y 中删除开头的公共(public)内容。然后将两个字符串的剩余长度相加。

例如

D(1111, 1000) = 只有第一个字母是常见的。所以剩下的字符串是 111 & 000。因此结果 length("111") & length("000") = 3 + 3 = 6

D(101, 1100) = 只有前两个字母是常见的。所以剩下的字符串是 01 & 100。因此结果 length("01") & length("100") = 2 + 3 = 5

很明显，如此疯狂的距离将是线性的。 O(m).

现在的问题是

给定 n 个输入，说喜欢

1111
1000
101
1100

找出可能的最大疯狂距离。

n 是输入字符串的数量。 m 是任何输入字符串的最大长度。

O(n² * m) 的解非常简单。可以用更好的方式完成吗？ 让我们假设 m 是固定的。我们可以比 O(n^2) 更好地做到这一点吗？

Answer 1

将字符串放入树中，其中 0 表示向左走，1 表示向右走。例如

1111
1000
101
1100

会产生像这样的树

        Root
             1
          0     1
         0 1*  0  1
        0*    0*    1*

* 表示元素到此结束。构建这棵树显然需要 O(n m) .

现在我们必须找到 diameter of the tree (两个节点之间的最长路径，与“疯狂距离”是一回事)。此处介绍的优化算法会命中树中的每个节点一次。最多有 min(n m, 2^m)这样的节点。

所以如果n m < 2^m ，则算法为 O(n m) .

如果n m > 2^m (而且我们必然有重复输入)，那么算法仍然是O(n m)从第一步开始。

这也适用于具有通用字母表的字符串；对于带有 k 的字母表字母构建k -ary 树，在这种情况下，根据相同的推理，运行时间仍然是 O(n m)，尽管它需要 k内存的两倍。