字符串操作算法

我读了一个字符串数组，例如：aaa bb ccccc ddd eeee fffffff ggggggg。我需要帮助处理一种算法，以便尽可能少地使用这些字符串，一行中字符的最大数量是一个固定值，例如15.如果向该行添加另一个字符串超过此值，我需要换一个新的路线。字符串操作算法

我想通过搜索，找到最大的字符串，然后与最小的连接，然后连接与下一个最大...等等将工作，但它没有达到我期望的结果，任何其他想法？

我需要看起来像输出：

AAA BB DDD EEEE FFFFFFF GGGGGGG

由于每一行上有15个charcters，这是你可能有线路的最小ammount的。

我正在使用C sharp。

来源

2012-03-27 rx432

你能解释一下吗？你在用什么语言工作？你想要什么样的输出？ – theJollySin 2012-03-27 03:03:16

DFS将是您的出发点。 http://en.wikipedia.org/wiki/Depth-first_search – hkf 2012-03-27 03:03:41

谢谢，我将有一个阅读，我需要输出到线上的字符串，在线上charcters的最大数量是15.我使用列表中的行，我只需要制定尽可能多的行上尽可能多的字符串，尽可能少的行。 – rx432 2012-03-27 03:06:20

我想你正在做的是一个半贪心算法，在这种情况下，它不会给你一个最佳的解决方案。最佳的解决方案可以通过使用诸如动态编程和备忘录之类的东西来找到。我会参考维基百科关于动态编程的文章中的例子。但要给你一个大致的想法，你想要做到以下几点：

开始用一大堆字符（任何大小）填充一行一旦你不能适应一个新的单词，检查是否添加左侧的单词， '而不是'该行中的一个单词会给你一个更好的填充报价。如果这样替换，如果不留下那个词，尝试一个新的。（我的意思是不同的大小，我假设你将所有相似大小的单词拼凑成相同的桶）一旦你尝试过所有大小，你可以移动到下一行，然后执行相同的操作，但是，还需要检查如果在第一行和第二行之间交换元素会给你一个更好的“全部”结果。实现这个可以在n^2中完成，但是有点棘手，如果你不关心计算效率，只要做这个蛮力。

来源

2012-03-27 03:15:40 Megalodon

字符串操作算法

回答

相关问题