用字典解析字符串的算法
给定的
- 一个充满单词的字典
{in, july, den, dentist, best, ...}和一些C++ API来访问它：boolean findWord(string word)，或者string getNextWord(void)来迭代它， - 一些没有空格的输入字符串，例如：
bestdentistinjuly.
输出
best dentist in july is...(基本上按照给定字典的空间分隔非空格字符串)
解决这个问题的最佳算法是什么？
一个微妙但重要的问题是，是否有任何奇妙的方法来解决无法到达的死胡同问题。例如，den和dentist都是剖析字符串其余部分的有效单词，其中一个可能只是一个死胡同。
在我看来，这似乎是一个贪婪的问题，或者是通过动态规划可以解决的问题。
回答 6
Stack Overflow用户
发布于 2011-07-20 18:54:26
使用Trie来存储字典。您可以在C#上看到一个简单的实现( 如何在c#中创建trie )
你需要做一个搜索，因为你不知道你是否在正确的轨道上，直到你考虑了整个输入字符串。您需要迭代输入字符串，同时下降到trie中。当您到达trie的终端节点时，您的搜索过程中有一个分支:您需要将其视为单词的结尾，并将其视为较长单词的第一部分。
Stack Overflow用户
发布于 2011-07-20 19:06:23
您可以创建一种单词树：
你可以在没有空格的情况下完成这个字符串。一旦你在你的列表中找到一个单词，你就添加一个空格，然后你继续.直到你不能走得更远。
然后，你回到之前的单词，试着选择如果添加新的字母，你可以创建一个词，如果你可以继续从他们的。
你试一试，直到你尝试了所有的可能性。
如果你回到原语，你找不到任何解决方案，=>，没有溶胶
这里是算法(我的伪代码语法不是很好，但你可以得到一般的想法。我相信你必须更正一下)：
TreeWordResult //Tree that keeps the results in memory
Go through the InputString:
If you find a word in the InputDictionnary
Then add this word to the last node of the treeWordResult
Otherwise:
while (No word found):
go back in the treeWordResult
try to find word in InputDictionnary different from the one before (on the other node)
endwhile
if no word found:
return NO SOLUTION
otherwise:
continue going through word
endif
endif
return Leaf 算法结束时，你没有发现溶胶，或当你在一个“叶子”(你去处理整个字符串)
这里是一个例子，用你的例子：
希望我的解释清楚。
Stack Overflow用户
发布于 2011-07-20 19:04:14
这个问题基本上就像匹配表单的正则表达式一样：
(in|july|den|dentis|best|...)*因此，任何正则表达式都可以使用。您应该选择哪一个取决于字典的大小和输入的长度。你应该从这里开始：《时代》
https://stackoverflow.com/questions/6766346
复制相似问题
腾讯云开发者
