algorithm - 拆分句子以最小化句子长度

Question

我遇到了以下问题陈述:

You have a sentence written entirely in a single row. You would like to split it into several rows by replacing some of the spaces with "new row" indicators. Your goal is to minimize the width of the longest row in the resulting text ("new row" indicators do not count towards the width of a row). You may replace at most K spaces.

You will be given a sentence and a K. Split the sentence using the procedure described above and return the width of the longest row.

我有点不知道从哪里开始。对我来说，似乎我需要尝试找出满足将单个句子分成 K 行的标准的每个可能的句子长度。

我可以看到一些极端情况:

1. 句子中有 <= K 个词，因此返回最长的词。
2. 句子长度为0，返回0

如果这两个条件都不成立，那么我们必须确定拆分句子的所有可能组合，并返回所有这些选项中的最小值。这是我不知道该怎么做的部分(显然是问题的核心)。

Answer 1

你可以通过反转问题来解决它。假设我将最长拆分的长度固定为 L。你能计算出满足它所需的最小拆分次数吗？

是的，您只需在第一个超过 L 的单词前换行，然后将它们加起来 (O(N))。

现在我们已经有了，我们只需要找到一个最小的 L，它需要少于或等于 K 的中断。您可以对输入的长度进行二进制搜索。最终复杂度 O(NlogN)。