Uber ATG

哦, 明白了,  是不是LC17的难度再提升一些了, 用LC17的方法把比如234的所有字母组合都找到,  然后看字典里面能匹配几个, 比如"234" 能匹配到2个,  然后找出能匹配做多的那个电话号码吗?

zhxymacau2017 发表于 2018-1-18 07:29
哦, 明白了,  是不是LC17的难度再提升一些了, 用LC17的方法把比如234的所有字母组合都找到,  然后看字典里 ...

对对对对

gnolli 发表于 2018-1-17 11:54
比如我有电话号码“234”，有单词表“ADG”, "ADH", "ABG"，那么电话号码234对应ADG和ADH；就是LC17题那 ...

最后楼主拿到onsite了不

zhxymacau2017 发表于 2018-1-18 07:29
哦, 明白了,  是不是LC17的难度再提升一些了, 用LC17的方法把比如234的所有字母组合都找到,  然后看字典里 ...

为什么要找出所有的字母组合？直接把所有的单词转化成电话号码，存在一个hash里，然后每一个电话号码找一下一共有几个对应单词应该会更快吧。

ntupenn 发表于 2018-1-24 08:51
为什么要找出所有的字母组合？直接把所有的单词转化成电话号码，存在一个hash里，然后每一个电话号码找一 ...

他让你考虑两种case，一种是电话号码数>>单词数，另一种是单词数>>电话号码数
反正hashmap瞎搞

gnolli 发表于 2018-1-24 08:54
他让你考虑两种case，一种是电话号码数>>单词数，另一种是单词数>>电话号码数
反正hashmap瞎搞

谢谢啦，这样就好理解了。

ntupenn 发表于 2018-1-24 09:04
谢谢啦，这样就好理解了。

但是感觉两种情况都是你说的思路更快吧。如果assume string len O(1) 那都是linear in 电话号码数+单词数 吧？
如果有啥没想到的区别 求指出~

gnolli 发表于 2018-1-24 08:54
他让你考虑两种case，一种是电话号码数>>单词数，另一种是单词数>>电话号码数
反正hashmap瞎搞

楼主可以细说一下这两种case算法选择上会有什么区别吗？我感觉都是先把单词转为电话号码更快啊。。

SvenSUTD 发表于 2018-1-25 01:25
但是感觉两种情况都是你说的思路更快吧。如果assume string len O(1) 那都是linear in 电话号码数+单词数 ...

主要看input是什么种类吧，如果都是array,那就是我的思路快，如果都是hash，那就根据哪个数据量大来选择算法。