狗家超短电面

T大农民伯伯 发表于 2018-11-27 07:19
为啥不建个哈希表直接搜索word是否存在哈希表中。

那样的话复杂度也是NL？N是text长度，L是word_dict最长词长度。Trie的话如果匹配失败可以提前退出性能会好一点？储存的空间占用在非最坏情况也比hashmap好一点？

PhantomFan 发表于 2018-11-28 04:52
那样的话复杂度也是NL？N是text长度，L是word_dict最长词长度。Trie的话如果匹配失败可以提前退出性能会 ...

如果用哈希表的话，我其实不知道时间复杂度有多大，我感觉是O(n). 因为你会把word字符串编码然后变成哈希表的key value. 这样也许查询为O(1). 但是相比于trie 存储空间上去了是肯定的。

PhantomFan 发表于 2018-11-28 04:51
嗯我也觉得是NL，然后我说的那个意思是，search for prefix的接口应该是找全所有存在于trie中的prefix， ...

明白了，谢谢！

T大农民伯伯 发表于 2018-11-28 06:00
如果用哈希表的话，我其实不知道时间复杂度有多大，我感觉是O(n). 因为你会把word字符串编码然后变成哈希 ...

对于长串每一个位置 从这里开始往前数1,2,...,L长的子串都需要判定是否在hashmap里。所以是NL？

PhantomFan 发表于 2018-11-28 07:42
对于长串每一个位置 从这里开始往前数1,2,...,L长的子串都需要判定是否在hashmap里。所以是NL？

我以为你再说热身题，之前分数不够看不到正式题，那确实是trie就可以了。

followup的一些解法，错了请指正。。。。

假设len(text)=m, len(words)=k, 一个word的长度为n
对于以下所有方法，由于允许跨过空格的搜索，所以直接把空格忽略掉即可
方法1：
对每个word在text里进行kmp，复杂度是m+kn (kmp算法的复杂度原本是m，但那主要是由于有一个建表的过程需要O(m)复杂度，然后再搜索需要O(n)复杂度。这题只要建一次表，所以是m+kn)

方法2：
给words做一个trie，然后对于text的每个前缀（即text[0:], text[1:], text[2:], text[3:]等）找trie有没有这个词
复杂度=nk+mn 空间26**n （但是一般词不会出现这么大的空间复杂度的）

方法3：
把text里的每一个substring（即text[0:], text[1:], text[2:], text[3:]….，text[0:-1], text[1: -1], text[2: -1], text[3: -1]…等）存进hashset, 然后在set里搜索words里的每个word是否存在
复杂度m**2+k 空间：m**2