gra*_*ter 13 algorithm complexity-theory search search-engine
我最近遇到了以下面试问题:
给定一个输入字符串和一个单词字典,实现一个方法,将输入字符串分解为一个空格分隔的字典单词串,搜索引擎可能会将其用于"你的意思是什么？" 例如,"applepie"的输入应该产生"苹果派"的输出.
就复杂性而言,我似乎无法获得最佳解决方案.有没有人对如何有效地做这个有任何建议？
小智 10
看起来问题正是我的面试问题,直到我在The Noisy Channel 的帖子中使用的例子.很高兴你喜欢这个解决方案.我敢肯定你无法击败我描述的最坏情况性能的O(n ^ 2)动态编程/ memoization解决方案.
如果你的字典和输入不是病态的,你可以在实践中做得更好.例如,如果您可以在线性时间中识别输入字符串的子字符串在字典中(例如,使用trie),并且如果这些子字符串的数量是恒定的,则总时间将是线性的.当然,这是很多假设,但真实数据往往比病态最坏情况好得多.
也有这个问题的有趣变化,以使其更难,如枚举所有有效分割的基础上,最好的一些定义输出最佳分割,处理字典太大,无法在内存中,处理不完全分割(例如,纠正拼写错误).欢迎在我的博客上发表评论或以其他方式联系我跟进.