c++ - 用字典解析字符串的算法

Question

给定

• 一个充满单词的字典 {in, july, den, dentist, best, ...} 用一些 C++ API 来访问它:boolean findWord(string word) ，或 string getNextWord(void) 遍历它，

• 一些没有空格的输入字符串，例如:bestdentistinjuly...

输出

• 7 月最好的牙医是...(给定字典，基本上用空格分隔非空格字符串)

解决它的最佳算法是什么？

一个微妙但重要的问题是，是否有任何奇特的方法来解决无法到达的死胡同问题。例如，den 和 dentist 都是剖析字符串其余部分的有效词，其中一个可能只是一个死胡同。

对我来说，这似乎是一个贪心问题或可以通过动态规划解决的问题..

Answer 1

使用 Trie 来存储字典。您可以在 How to create a trie in c# 查看一个简单的实现 (C#)

您将需要进行搜索，因为在考虑了整个输入字符串之前您不知道自己是否在正确的轨道上。您需要遍历输入字符串，同时下降到 trie 中。当您到达 trie 的终端节点时，您的搜索过程中有一个分支:您需要将其视为单词的结尾并将其视为较长单词的第一部分。