G家实习电面挂经

已注销用户-D3F3 发表于 2016-11-10 06:46
你这个跟楼主的解法没有区别，跟楼上提出的解法类似的复杂度。 我一上来的idea就是读一遍S，然后存下map 跟 ...

双指针空间就是O（1）的。

catinclay 发表于 2016-11-10 05:33
直接用hashmap存所有prefix的last index in original string会不会比较快?

你是说用unordered_map<Node*, int>lastIdx来存字典中每个prefix (1-1对应一个Trie node)的最后字母在s总的位置吗？这样当（node->isWord = true && lastIndex[node]<s.length） 时, node的最深层深度就是可匹配的最长单词。但是要计算每个lastIndex[node]还是得依赖于char在s.subtr(j)中第一次出现的位置(我定义的pos)。这个好像时间是一样的, 还是把"start"在dfs中传下去。

primbo 发表于 2016-11-10 05:41
楼主不是用这种方法了么，面试官说不行。

关键是LZ没有对字典进行处理，每个单词单独处理，所以时间和单词个数完全成正比。这对于字典中单词很多但公用prefix也很多的情况下就很浪费时间了。

prodigalr 发表于 2016-11-10 07:06
双指针空间就是O（1）的。

双指针空间的确是O（1）的。但每次处理一个单词的时间都是O(s.length)，所以最后总时间O(s.length*dict.size())不是最优的，但空间的确是最优的。
若只让比较一个string word是不是另一个string s的subsequence, 双指针方法完全没有问题。关键这个题的考点相当于需要多次调用对于大量的words时，如何节约时间？若不预处理还是把所有的word完全独立对待就会有重复浪费

可以把所有的words做成一个Trie，再用S来搜索。
大概写一下思路。

1. def search(i, node):
   
2.     if i >= len(S):
   
3.         return
   
4.     result += node.isWord
   
5.     if S[i] in node.children:
   
6.         search(i+1, node.children.pop(S[i])
   
7.     search(i+1, node)

复制代码

谢谢楼主的分享！同问能麻烦给下recruiter的邮箱吗？被推了三周了一直都还没消息 怕是被漏了

zzgzzm 发表于 2016-11-9 12:00
第二面：这个题等价于求string s中的最长subsequence found in dictionary（注意是subsequence，不是substr ...

太厉害了。。。。不过面试的时候怎么能想到这个的。。。

dokolo 发表于 2016-11-10 11:08
可以把所有的words做成一个Trie，再用S来搜索。
大概写一下思路。

思路和我类似 但是code实现感觉不容易 好多次recursion 你可以记录trie里面每个node在s里面的index，isword的时候检查是不是-1，如果是-1就不需要继续call了....反正就这样吧。。感觉time complexity是n*m + k*l， m是node多少。。l是average length word in dict， k是dict size，n是s length

zzgzzm 发表于 2016-11-10 07:20
你是说用unordered_maplastIdx来存字典中每个prefix (1-1对应一个Trie node)的最后字母在s总的位置吗？这 ...

嗯 貌似你说的是对的

cookielee77 发表于 2016-11-10 13:27
太厉害了。。。。不过面试的时候怎么能想到这个的。。。

用二维dp[][]好像不必要。我又写了个改进的在30层，就是直接pre-order traversal Trie （DFS, 不要在s.substr(j)的j上DP）.
说实在的，我觉得这个放在电面的确难。