将字符串拆分为单词

Question

我正在寻找最有效的算法来形成字符串中所有可能的单词组合.例如:

Input String: forevercarrot

Output:

forever carrot
forever car rot
for ever carrot
for ever car rot

(所有单词都应该来自字典).

我可以想到一个蛮力的方法.(找到所有可能的子串并匹配)但是更好的方法是什么？

Answer 1

使用前缀树作为已知单词列表.也许lib myspell已经这样做了.尝试使用现成的.

一旦你找到一个匹配(例如'car'),就分开计算:一个分支开始寻找一个新单词('rot'),另一个分支继续探索当前开始的变种('carrot').

(start_position, current_position)每次分割计算时,有效地将字符串对的队列维护到字符串中.几个线程可以并行地从这个队列中弹出,并尝试继续一个从该对开始start_position并且已经知道current_position该对的单词,但不会在那里结束.找到某个单词时,会报告该单词,并从队列中弹出另一对.当它不可能时,不会产生任何结果.发生拆分时,会在队列末尾添加一对新对.最初队列包含一个(0,0).

Answer 2

伪代码实现，利用字符串的每个部分都需要是单词的事实，我们不能跳过任何内容。我们从字符串的开头向前工作，直到第一位是单词，然后生成字符串其余部分的所有可能组合。一旦我们做到了这一点，我们就会继续下去，直到我们找到第一个单词的任何其他可能性，依此类推。

allPossibleWords(string s, int startPosition) {
    list ret
    for i in startPosition..s'length
        if isWord(s[startPosition, i])
            ret += s[startPostion, i] * allPossibleWords(s, i)
    return ret    
}

这段代码中的问题是您最终将重复计算 - 在您的示例中，您最终将不得不计算allPossibleWords("carrot")两次 - 一次 in["forever", allPossibleWords["carrot"]]和一次 in ["for", "ever", allPossibleWords["carrot"]]。所以记住这一点是需要考虑的。