SnapChat OA passed 9/10 test cases

题目还是Easy / Compound单词那个。

1. given an array of words. output array of simple words. compound word are made of multiple simple words in the array.
   
2. 
   
3. Example input:
   
4. String[] = {chat ever snapchat snap salesperson per person sales son whatsoever what so}
   
5. 其中simple word是: chat, ever, snap, per, sales, son, what, so
   
6. 
   
7. 尤其注意son是simple

复制代码

我使用的是基于长度Sorting + Set + Iterative的Word Break（）思路仍然只过了其中9个。

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

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

):
上午告诉HR做完了，下午拿到了电面邀请。所以和之前一样，并不是要求10个test cases都要过。当然，能都过最好~

用trie 好像能有 O（N）的时间

上午告诉HR做完了，下午拿到了电面邀请。所以和之前一样，并不是要求10个test cases都要过。当然，能都过最好~

用dfs 剪枝是可以通过的。其实dp hit 到 word的长度时候 立即返回 应该也是 能通过的。 我之前先用dp也是发现最后一个过不了，然后立即改成剪枝版本的dfs就过了。事后想想其实dp提前返回应该跟dfs一样的效果。

cx00001 发表于 2016-4-3 14:40
用dfs 剪枝是可以通过的。其实dp hit 到 word的长度时候 立即返回 应该也是 能通过的。 我之前先用dp也是发 ...

请教一下同学， dfs能剪哪些枝啊？
除非你用trie 做了startWith 判断，不然没法剪啊

就是backtracking

Java自带的sort应该是优化最好的，这点可以从leetcode运行时间看出来。会根据具体情况选择计数排序等非比较排序。

排序没用 通不过三个例子

最后一个test没有过是因为 有可能输入里含有空string “”  这样的话 这个也算是simple word 如果你没有把这个加到最后的结果里 就会fail最后一个test 并不是因为超时 所以我觉得这种edge case他们应该也不是很在意

并不是空串 空串根本进不了循环 就是超时了 dp用向后看的那个方法 hit到最后一个位置立即返回就可以通过了