谷歌访谈:找到字符串之间的疯狂距离

Question

谷歌采访时向我询问了这个问题.我能做到O(n*n)......我可以在更好的时间做到这一点.字符串只能由1和0组成.

定义:

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

D(X,Y) =从X和Y开始删除开头常见的东西.然后从两个字符串中添加剩余的长度.

例如

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输入,比如说

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

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

O(n ²*m)的解决方案非常简单.它能以更好的方式完成吗？我们假设m是固定的.我们能比O(n ^ 2)做得更好吗？

Answer 1

将字符串放入树中,其中0表示向左移动,1表示向右移动.所以举个例子

会导致树像

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

其中*表示元素在那里结束.明确地构建这棵树O(n m).

现在我们必须找到树的直径(两个节点之间的最长路径,这与"疯狂距离"相同).在那里呈现的优化算法命中树中的每个节点一次.最多有min(n m, 2^m)这样的节点.

所以如果n m < 2^m,那么算法就是O(n m).

如果n m > 2^m(并且我们必须重复输入),那么算法仍然O(n m)是第一步.

这也适用于具有通用字母表的字符串; 对于带k字母的字母表构建一个k单独的树,在这种情况下运行时仍然是O(nm)相同的推理,虽然它需要k多少内存.