最小化每组长度的连续单词分组算法

Question

从输入的 space 分隔的单词中，如何连接连续的单词以便：

每组最小长度为L（spaces不算）
最长的组长度是最小的（spaces 不算）

示例输入：

would a cat eat a mouse

示例最小长度：

L = 5

解决第一个条件但不解决第二个条件的朴素算法：

while length of a group is less than L, concatenate next word to group
if last group is shorter than L, concatenate last two groups together

这个朴素的算法产生：

第 1 组：会[=43=]
第 2 组：acateat
第 3 组：老鼠
最长组长度：7

第二个条件未解决，因为更好的解决方案是：

第 1 组：woulda
第 2 组：cateat
第 3 组：老鼠
最长组长度：6

哪种算法可以作为程序以相对较快的执行速度解决第二个条件（最小最长组）？（通过快速，我想避免测试所有可能的组合）

我知道 C、ObjC、Swift、Javascript、Python，但伪代码很好。

Answer 1

这可以通过动态规划方法来完成。让我们计算一个函数 F(i) - 将前 i 个单词正确划分为组的最长组的最小长度。

F(0) = 0
F(i) = Min(Max(F(j), totalLen(j+1, i))), for j in [0..i-1]

哪里

totalLen(i, j) = total length of words from i to j, if the length is at least L 
totalLen(i, j) = MAX, if total length is less than L

答案是F(n)的值。为了获得组本身，我们可以为每个 i.

保存最佳 j 的索引

在c++中有一个从头开始的实现：

const vector<string> words = {"would", "a", "cat", "eat", "a", "mouse"};
const int L = 5;
int n = words.size();

vector<int> prefixLen = countPrefixLen(words);

vector<int> f(n+1);
vector<int> best(n+1, -1);
int maxL = prefixLen[n];
f[0] = 0;

for (int i = 1; i <= n; ++i) {
    f[i] = maxL; 
    for (int j = 0; j < i; ++j) {
        int totalLen = prefixLen[i] - prefixLen[j];
        if (totalLen >= L) {
            int maxLen = max(f[j], totalLen);
            if (f[i] > maxLen) {
                f[i] = maxLen;
                best[i] = j;
            }
        }
    } 
}

output(f[n], prev, words);

预处理和输出细节：

vector<int> countPrefixLen(const vector<string>& words) {
    int n = words.size();
    vector<int> prefixLen(n+1);
    for (int i = 1; i <= n; ++i) {
        prefixLen[i] = prefixLen[i-1] + words[i-1].length();
    } 
    return prefixLen;
}

void output(int answer, const vector<int>& best, const vector<string>& words) {
    cout << answer << endl;

    int j = best.size()-1;
    vector<int> restoreIndex(1, j);
    while (j > 0) {
        int i = best[j];
        restoreIndex.push_back(i);
        j = i;
    }
    reverse(restoreIndex.begin(), restoreIndex.end());
    for (int i = 0; i+1 < restoreIndex.size(); ++i) {
        for (int j = restoreIndex[i]; j < restoreIndex[i+1]; ++j) {
            cout << words[j] << ' ';
        }
        cout << endl;
    }
}

输出：

6
would a 
cat eat 
a mouse

可运行：https://ideone.com/AaV5C8

进一步改进

这个算法的复杂度是O(N^2)。如果它对你的数据来说太慢了，我可以建议一个简单的优化：

让我们反转内部循环。首先，这允许摆脱 prefixLen 数组及其预处理，因为现在我们将单词一个一个地添加到组中（实际上，我们可以在初始版本中摆脱这种预处理，但代价是简单）。更重要的是，当 totalLen 不小于已计算的 f[i] 时，我们可以打破循环，因为进一步的迭代永远不会带来改进。内循环的代码可以改成：

int totalLen = 0;
for (int j = i-1; j >= 0; --j) {
    totalLen += words[j].length();
    if (totalLen >= L) {
        int maxLen = max(f[j], totalLen);
        if (f[i] > maxLen) {
            f[i] = maxLen;
            best[i] = j;
        }
    }
    if (totalLen >= f[i]) break;
}

这可以显着提高 L 值不是很大的性能。

最小化每组长度的连续单词分组算法

Algorithm to group consecutive words minimizing length per group

string

algorithm

objective-c

pseudocode