您会得到一个不带任何空格的字符串示例“Iamastudent”。您将获得一个预定义的字典功能，该功能可验证给定单词是否存在于字典中。使用此功能，您必须在字符串中插入空格并将其打印为“我是学生”。
这是我的面试问题，并告诉我也用 C++ 解决，我使用动态编程解决了它，但他不满意我给出的解决方案与下面的问题相同
他让我使用trie或后缀数组来做，但我想不出任何人都可以帮助我的解决方案
user1814884
问问题
1009 次
2 回答
0
答案是使用 Trie 数据结构。用可能的单词创建 Trie 并继续遍历。使用 Trie，您可以生成许多不同的可能单词。
现在在这里“iamastudent”和 Trie 你可以生成这些词。
i, a, am, a, as, student
现在你必须用这些词造一个合适的句子。这里可能的解决方案是马尔可夫链。马尔可夫链是一种数据结构，它保存一个单词之后的下一个单词的概率。所以马尔可夫链会。
"i" : [ "am", "did", "went" ...],
"a" : [ "tree", "dog" ..]
"am" : [ "a" ...]
现在你按顺序排列了这么多数据
[i], [a, am], [a, as], [student]
注意：我将所有以相同字符开头的元素分组到一个列表中。
以“i”开头的 下一个单词是“a”。但在马尔可夫链中，“a”不存在。所以去下一个词。像这样你可以继续。
从这里开始，它是对有效句子的 dfs 搜索。嗯，这是一个很好但很棘手的问题。
于 2017-10-21T01:48:57.257 回答
-1
如果存在拆分句子的独特解决方案，那么使用 trie 进行拆分很简单：
- 如果输入字符串中有字符，则从根开始向下走，消耗字符串中的字符。否则终止。
- 如果它是一个压缩的 trie，只要前缀是一个完整的单词，你就会找到一个标记，否则如果你到达一个叶子，那就是你输出一个空格
- 从字符串中的当前位置开始返回 1（从根向下走）
当字符串中没有更多字符时，您就完成了（您可能想要检查此时您没有遍历树）。
如果解决方案不是唯一的，那么每当您到达字符串的末尾并且您不在树中的标记或叶子处时，您需要回溯到您发出的前一个空间。您需要一个堆栈来存储输入字符串中的位置。
于 2013-07-21T15:44:21.170 回答