从删除空格和重新排序单词字母的句子中重构句子的算法？

Question

我在网上浏览了一些拼图，以提高我对算法的了解……

我遇到了以下问题：

“您有一个句子，其中几个单词删除了空格，单词的字符顺序被打乱。您有一本字典。编写一个算法，以正常字符顺序重新生成包含空格和单词的句子。”

我不知道什么是解决这个问题的好方法。

我对算法是个新手，但只要看看问题，我想我会让程序做一个智力思维会做的事情。

下面是我能想到的一些事情：

-First从字典中手动查找常见的短英语单词，如"is“、"if”等，并将其放入dataset-1中。

-Then找出dataset1中单词的排列(例如"si“、"eht”或"eth“或"fi")，并将其放入dataset-2

-then从输入句子中找出与dataset2的单词匹配的字符序列，并将它们放入dataset-3中，并在输入句子中插入空格，而不是那些找到的单词。

对于其余的单词，我会执行排列，以便从字典中查找单词。-for。

我是新手来algorithms...is它是一个糟糕的解决方案吗？

Answer 1

这看起来是个很好的解决方案，

一般来说，有两个参数来判断一个算法。

1. 正确性-算法是否提供了正确的answer.
2. resources -提供答案所需的时间或存储大小。

通常在这两个参数之间存在权衡。

例如，你的字典的大小决定了你可以重构哪些混乱的句子，对于更多的输入，你会得到一个正确的答案，但是整个搜索过程需要更长的时间和更多的存储空间。

您提出的问题的难点在于，您需要计算排列，并且存在大量的排列。( LOT )

因此，检查所有这些单词是昂贵的，一个好的方法是按照您的建议，创建一个常用单词的一个小子集，然后首先检查它们，这样平均情况会更好。

注意：只是说你检查排列/搜索是可以的，但最终你需要指定具体的方法。

目前，你写的是一个算法的想法，但它不允许你接受给定的输入并机械地计算出输出。

Answer 2

实际上，明智的做法是先按单词长度对字典进行划分。

然后试着找出最大的单词，而不是找最小的单词。短词更常见，因此更难缩小范围。真的是“如果”还是“无花果”。

然后，对于每个单词长度w，您可以一次处理w个字符。

然而，仍然有很多可能的组合，仅仅因为你找到了一个有效的单词，并不意味着它就是正确的单词。浏览完所有子字符串后，应该有类似O(c^4*d)的内容，其中d是字典中的单词数，c是句子中的字符数。实际上，如果字典是按单词长度排序的，那么它会比这个少得多。然后，您必须获取有效的单词，并找出有效的排序，以便使用所有字符。可能有多种解决方案。