Google OA 一道 附完整代码

两个字符串的距离定义为除去共同前缀后两字符串长度只和。给一个二元字符串列表，请给出距离最大的两个字符串的距离。

这个暴力破解的话也不难，时间复杂度O(m*n^2), 其中m为字符串平均长度。

另一个解法是用Trie. 完整代码见下方。希望大家多多给点大米，非常感谢！ 直接给代码毕竟太赤裸裸， 后面会尽量降hide的threshold的。
[hide=200]class TrieNode:
    def __init__(self, depth):
        # self.char = char
        self.left = None
        self.right = None
        self.isEnd = False
        self.depth = depth

    def get(self, c):
        if c == '1':
            return self.right
        else:
            return self.left

    def set(self, c):
        if c == '1':
            self.right = TrieNode(self.depth + 1)
        else:
            self.left

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

test1(self):
        words = ['1011000', '10111101', '1100000']
        self.setup(words)
        distance = self.trie.root.maxDistance()
        print('max_distance between words ', words, distance)

test = Test()
test.test1()



补充内容 (2019-9-19 03:11):
使用Trie以后时间复杂度是O(mn), 把m看做常数的话，这就是线性时间的解

Gtjobs 发表于 2019-9-18 23:40
这个OA只有一道吗 楼主

另一道晚点出，我还没整理好

a289206397 发表于 2019-9-18 22:57
楼主这是new grad的OA？不是浇花和多米诺了？

那两道可能比较常见吧，但是其实还有很多别的题……

楼主这是new grad的OA？不是浇花和多米诺了？

那两道可能比较常见吧，但是其实还有很多别的题……

这个OA只有一道吗 楼主

楼主你这个hide没有activate，最后加一个[/hide]...

lz这个比浇花和多米诺麻烦多了，还好做的早

感谢楼主分享！！！！

求分享求交流。字数字数字数