algorithm - 最大化以特定字符结尾的行数

Question

给你一行字符串，每个单词由空格分隔。您只能在字符串的第 5-10 列中插入新行。您的目标是最大限度地增加以字符 x 结尾的行数。例如，你会怎么做。

编辑:单词可以以任何字符结尾，假设给定了文本

abcdfg cdx abcdx abcdefg aa ggffx ax

那么显示它们的方式就是

column:
1234567890
abcdfg cdx
abcdx
abcdefg 
aa ggfx
ax

这会最大化结果，因为它有 4 行以 x

结尾

我觉得这道题真正的问题是，如果它不是以x结尾，而且是在一个可以break的位置，我们怎么break。

观察

abcdefg 
aa ggfx
ax

如果 aa 与 abcdefg 在第一行，那么我们将只能再多一行 x，因为 ggfx 不能立即中断。结果 ggfx ax 将在同一行

Answer 1

每当您可以断行并遇到合适的字符时就断行。如果接下来的九个中没有目标字符，则一直打破。

不幸的是，这将给出最佳答案。这是一个简单的游戏。

如果我们可以对在某些列范围内(例如，第 8-10 列)具有目标字符的行进行评分，那将会更有趣。但只计算最后一列，贪心占了上风。

我在这里假设您可以在不必连字符或其他任何东西的情况下切碎单词。但是您没有给我们其他规则，那么我还能做出什么其他假设？

String str = "000x0dfkdfjfxxiwrhx fsjhfx fwuhxjhfe xj etc etc you get it";
int doneidx = 0;
char targetchar = 'x';
StringBuffer tmp = new StringBuffer();
while (doneidx < str.length()) {
    if (tmp.length() < 5) {
        tmp.append(str.charAt(doneidx));
    } else {
        for (int i = 0; i < 6; i++) {
            if (doneidx+i < str.length() && str.charAt(doneidx+i) == targetchar) {
                tmp.append(str.substring(doneidx, doneidx+i+1)); 
                doneidx += i+1;
                break;
            }
        }
        System.out.println(tmp.toString());
        tmp = new StringBuffer();
    }
}

这是一个复杂度为 O(N^2) 的算法。使用记忆化可以将其减少到 O(N)。但是，老实说，我认为这并不重要。