字符串操作算法

我讀了一個字符串數組，例如：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

字符串操作算法

回答

相關問題