c++ - 给定一个单词，通过在它们之间添加空格来形成一个有意义的单词

Question

给你一个没有任何空格的字符串示例“Iamastudent”。您将获得一个预定义的词典功能，该功能可验证给定单词是否存在于词典中。使用此函数，您必须在字符串中插入空格并将其打印为“I am a student”。

这是我的面试题，告诉我也用 C++ 解决了，我用动态规划解决了，但他不满意我给出的解决方案是 与下面的问题相同

Given a phrase without spaces add spaces to make proper sentence

他让我用 trie 或 suffix array 来做，但我无法想出任何人都可以帮助我的解决方案

Answer 1

Find words and put spaces after them

答案是使用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] 

Note: I grouped all elements which starts with same character in one list.

以“i”开头下一个词是“a”。但在马尔可夫链中，“a”不存在。所以去下一个词。这样你就可以继续了。

从这里开始，它是一个有效句子的 dfs 搜索。好吧，这是一个很好但很棘手的问题。