algorithm - 将字符串分解为一系列单词

Question

我最近遇到了以下面试问题:

Given an input string and a dictionary of words, implement a method that breaks up the input string into a space-separated string of dictionary words that a search engine might use for "Did you mean?" For example, an input of "applepie" should yield an output of "apple pie".

就复杂性而言，我似乎无法获得最佳解决方案。有人对如何有效地执行此操作有任何建议吗？

Answer 1

看起来这个问题正是我的面试问题，具体到我在 post 中使用的示例在嘈杂的 channel 。很高兴您喜欢这个解决方案。我很确定您无法击败我描述的最坏情况性能的 O(n^2) 动态编程/内存解决方案。

如果您的字典和输入不是病态的，您可以在实践中做得更好。例如，如果您可以在线性时间内识别输入字符串的子字符串在字典中(例如，使用 trie)并且如果此类子字符串的数量是常数，则总时间将是线性的。当然，这是很多假设，但实际数据通常比病态的最坏情况要好得多。

这个问题也有一些有趣的变体使它变得更难，例如枚举所有有效的分割，根据最佳的某些定义输出最佳分割，处理太大而无法放入内存的字典，以及处理不精确的分割(例如, 纠正拼写错误)。请随时在我的博客上发表评论或以其他方式与我联系以跟进。