我正在寻找最有效的算法来构成字符串中单词的所有可能组合。例如:
Input String: forevercarrot
Output:
forever carrot
forever car rot
for ever carrot
for ever car rot
(所有单词都应来自词典)。
我可以想到一种蛮力的方法。 (找到所有可能的子字符串并匹配)，但是哪种更好的方法呢？
最佳答案
将prefix tree用于您的已知单词列表。像myspell这样的库可能已经这样做了。尝试使用现成的。
找到匹配项(例如“汽车”)后，请拆分计算内容:一个分支开始寻找新单词(“腐烂”)，另一个分支继续探索当前开始的变体(“胡萝卜”)。
实际上，每次拆分计算时，您都会在字符串中维护一对偶数偏移量(start_position, current_position)队列。多个线程可以并行地从此队列弹出，并尝试继续一个从start_position开始的单词，直到该对的current_position为止都知道，但没有到此为止。找到单词后，将报告该单词，并从队列中弹出另一对单词。如果不可能，则不会产生任何结果。发生拆分时，新对将添加到队列的末尾。最初，队列包含(0,0)。
关于algorithm - 将字串分割成字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4755157/