优步 简单的店面

刚刚面的店面需要在codepair里面run test case的
题目大概是这样
先给你一个字典
["this", "hi", "his", "is", "word"

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

搜索的时候考虑字典里面的最长字串长度
就可以不用去考虑过长的字串的情形
复杂度是O(N^2)

面试官好像很喜欢我的解法
大家讨论看看还有没有什么更好的解法吗

一般要输出所有可能情况的，DP解决不了的吧，你这个方法挺好的，没问题啊

严格来说可以用kmp把复杂度降到O(m*n)...m = string.length, n = set.size.... pros and cons...

catinclay 发表于 2016-11-17 04:29
严格来说可以用kmp把复杂度降到O(m*n)...m = string.length, n = set.size.... pros and cons...

所以是把字典裡的字一個一個拿LC裡面那道strStr()的作法對input字串掃過一遍
對吧
看來該好好了解一下KMP算法

tj474474 发表于 2016-11-17 09:17
所以是把字典裡的字一個一個拿LC裡面那道strStr()的作法對input字串掃過一遍
對吧
看來該好好了解一下K ...

对于一个SET里的这么多字符串,KMP怎么做？

catinclay 发表于 2016-11-17 04:29
严格来说可以用kmp把复杂度降到O(m*n)...m = string.length, n = set.size.... pros and cons...

对于一个SET里的这么多字符串,KMP怎么做？

我设想应该可以用一种高级KMP
Build a 3d matrix where the entry Wi Wj k is the index we should start in Wj if we failed to match Wi at k_th character.
Then you keep a counter for each word while iterating through the searched string, and apply the KMP method to update counters as needed...

感觉用trie还是O(n^2)所以面试官不在乎

另外dp应该不太适用于print all的情况吧(好像这么generalize也不对)

问下lz最后过电面了么