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

Question

从输入的空格分隔的单词中，如何连接连续的单词以便:

• 每组的最小长度为L(空格不算)
• 最长的组长度是最小的(空格不算)

示例输入:

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 组:会
• 第 2 组:动物
• 第 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 值，这可以显着提高性能。