3

我正在网上寻找一些谜题以提高我对算法的了解......

我遇到了以下问题:

“你有一个句子,其中有几个单词删除了空格,单词的字符顺序被打乱了。你有一本字典。编写一个算法来生成带有空格和正常字符顺序的单词的句子。”

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

我是算法的新手,但只是看着问题,我想我会让程序做一个智力头脑会做的事情。

这是我能想到的:

-首先从字典中手动找出常见的短英文单词,如“is”“the”“if”等,并放入dataset-1。

-然后找出数据集1中单词的排列(例如“si”,“eht”或“eth”或“fi”)并放入数据集2

-然后从输入句中找出与数据集2的单词匹配的字符序列并放入它们在 dataset-3 中并在输入句子中插入空格而不是找到的那些。

- 对于其余的单词,我会执行排列以从字典中找出单词。

我是算法的新手......这是一个糟糕的解决方案吗?

4

2 回答 2

1

这似乎是一个完美的解决方案,

一般来说,判断一个算法有2个参数。

  1. 正确性——算法是否提供正确的答案。

  2. 资源 - 提供答案所需的时间或存储大小。

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

因此,例如,您的字典的大小决定了您可以重建哪些打乱的句子,从而为您提供更多输入的正确答案,但是整个搜索过程将花费更长的时间并且需要更多的存储空间。

您提出的问题的难点在于您需要计算排列,而且排列很多

所以检查它们都是昂贵的,一个好的方法是按照你的建议做,创建一小部分常用词并首先检查它们,这样平均情况会更好。

注意:只是说您检查排列/搜索没问题,但最后您需要指定执行此操作的确切方式。

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

于 2012-12-24T07:44:42.820 回答
0

实际上,从按字长对字典进行分区开始可能是明智的。

然后尝试找到可以使用可用字母组成的最大单词,而不是找到最小的单词。短词更常见,因此更难缩小范围。IE:真的是“如果”还是“无花果”。

然后对于每个字长 w,您可以一次处理 w 个字符。

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

于 2012-12-24T12:06:54.830 回答