从输入的空格分隔的单词中,如何连接连续的单词以便:
- 每组的最小长度为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,但伪代码很好。
最佳答案
这可以通过动态规划方法来完成。让我们计算一个函数 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
进一步改进
这个算法的复杂度是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
值,这可以显着提高性能。
关于objective-c - 最小化每组长度的连续单词分组算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46845103/