Google电面

第一题用trie树？

virpro 发表于 2016-10-8 01:50
如果同一个character有两个最长的String你怎么解决？比如hello, heard。

我们没讨论任何corner case，我代码里貌似就默认找第一个了。。

aisingioro 发表于 2016-10-8 02:09
第一题用trie树？

我也提供了这种思路 然后小哥说这和hashmap有啥区别 我说没区别都是O（N）。。所以就还是写的hashmap。。

请问第二题到底是啥意思，是指把这个list里的单词在屏幕上全部显示出来有多少种排列方法么？

同问，第二题的输出2是怎么来的

感觉就是这题：https://www.careercup.com/question?id=5701279419465728

第二题已光荣登上lc大榜 https://leetcode.com/problems/sentence-screen-fitting/

兰台 发表于 2016-10-8 03:56
我也提供了这种思路 然后小哥说这和hashmap有啥区别 我说没区别都是O（N）。。所以就还是写的hashmap。。

谢谢楼主分享！输入的list里只是char, 感觉hash map更简单；如果是不定长度的的string作为prefix，还是trie好点

我的第一题思路：
一扫描dict，找出最长字符串长度
二扫描dict，找出所有最长长度字符串，收入一个hashmap，key为首字母，value为一个arraylist的字符串
然后遍历list(首字母)，从hashmap中get值，组成结果。
复杂度应该是O(n) n=dict 长度