2016/09/07 电面

lyoaix 发表于 2016-9-10 01:32
我的第一反应也是建trie 然后就可以直接找了

但是怎么建这个trie呢，感觉是不是还是得先sort dict里的words。。。求大神给点思路～～

其实我想问一下，这个题怎么用trie做。我觉得不好啊。
sort之后插到trie 那xyz 树里的都是 abc abxyz 这种 怎么办？ 虽然一样可查。。不觉得效率很低吗？
毕竟trie查前缀好，这种好像不怎么样吧。。。

想法是把dictionary里的所有word sort后放入trie中(记得保存sort之前的值)，然后车牌的字典也sort，在trie中查

johnjavabean 发表于 2016-10-3 09:30
想法是把dictionary里的所有word sort后放入trie中(记得保存sort之前的值)，然后车牌的字典也sort，在trie ...

怎么查。。abczxy abs  车牌是zxy 这样不是前缀不会不好吗？

我觉得这个题建 trie 会有问题。 假设有词典中有两个词"axx", "xxxx". 你的拍照是 "xx"。 这种情况下 你是不是找到的最短的是xxxx？
想了下, 还不如就和19楼说的那样遍历 dict， 根据车牌可能可以稍微做下优化。觉得车牌 应该是前面两个char， 后面最多2个char。 建一个map， key是26*26 的字幕组合，value是一个list， 根据词长排序。然后一个个查char 频统计是否ok。感觉这题的特征是牌照上的字母很少， 但是应该有更好的方法。

是不是就是 https://leetcode.com/problems/minimum-window-substring/

printf_ll 发表于 2016-10-8 00:55
是不是就是 https://leetcode.com/problems/minimum-window-substring/

不太一样吧，leetcode是substring的字母顺序不变，这道题是可以变的，只要包含所有字母就行

补充内容 (2016-10-8 02:35):
哦，我记错了，你说的是对的