Google 电面

问一下，如果给的单词里有dog 也有dogg，他们的输出分别应该是什么呢？

谢谢lz了，我感觉可以用trie tree做，PS电面不容易！

思路是不是这样啊？

扫一遍input array， 建一个trie（前缀树），搜到每个单词，向上查找，直到parent有大于一的children stop，当前node就是要找的结果。
e.g.
                                     （）
                                       |
                                    （d）
                                    /      \
                            （do）       （du）
                             /      \           \
                    （dog） （dot） （duck）

dot 向上 do有2 children，所以 dot本身就是结果
duck-->du-->d,d有2个children，所以du就是结果

xperzy 发表于 2014-10-27 05:08
思路是不是这样啊？

扫一遍input array， 建一个trie（前缀树），搜到每个单词，向上查找，直到parent有 ...

请问：ab，abb，abbb这种情况怎么办，第一个word是后面word的一个前缀

byrlhb 发表于 2014-10-26 10:44
sorry，想错了，要更复杂一些

没错的。应该就是这样的。在Trie的每个中间节点加一个count field，插入的时候，count++，最后输出的时候，输出count为1的最高的那个点

unclewang 发表于 2014-10-27 02:10
问一下，如果给的单词里有dog 也有dogg，他们的输出分别应该是什么呢？

应该还是一样的把

xperzy 发表于 2014-10-27 05:08
思路是不是这样啊？

扫一遍input array， 建一个trie（前缀树），搜到每个单词，向上查找，直到parent有 ...

如何向上查找，难道你要建立双向的trie?
我当时也是提高这样的思路，但是感觉写不出来。。。

Arthur2012 发表于 2014-10-27 05:13
请问：ab，abb，abbb这种情况怎么办，第一个word是后面word的一个前缀

你给出的例子类似：
[bearcat, bear]
{bearcat: bearc, bear: ""}

所以应该是 abbb:abbb;abb:"";ab:""

happysshao 发表于 2014-10-27 11:56
你给出的例子类似：

{bearcat: bearc, bear: ""}

谢谢lz，lz一定会拿到onsite的，人品这么好！

Arthur2012 发表于 2014-10-27 12:10
谢谢lz，lz一定会拿到onsite的，人品这么好！

谢谢了！