c++ - 需要帮助实现将文本填充到特定宽度的特定逻辑。

Question

任务是在一定宽度内对齐文本。

user inputs: Hello my name is Harrry. This is a sample text input that nobody 
             will enter.

output: What text width do you want?

user inputs: 15

output: |Hello  my  name|
        |is Harrry. This| 
        |is   a   sample|
        |text       that| 
        |nobody     will|
        |enter.         |

基本上，该行必须有 15 个空格宽，包括空格。此外，如果行中的下一个单词不能放入 15，它将完全跳过。如果一行中有多个单词，它会尝试在每个单词之间平均分配空格。例如，参见“Is a sample”这一行。

我使用 getline(...) 创建了一个 vector ，所有这些和整个文本都保存在一个 vector 中。但是，我有点坚持前进。我尝试使用多个 for 循环，但我似乎无法跳过行，甚至根本无法超出间距。

同样，不期待或期望任何人解决这个问题，但如果你能指导我在我应该考虑的逻辑/算法方面走向正确的方向，我将不胜感激。

Answer 1

您应该考虑这个动态编程解决方案。

将文本拆分成“好的”行

由于我们不知道我们需要在哪里断行才能得到充分的理由，所以我们开始猜测要在该段落的什么地方断行。 (也就是我们猜测是否应该在两个单词之间打断，让第二个单词作为下一行的开始)。

你注意到什么了吗？我们蛮干的!

请注意，如果我们找不到足够小的词来适应当前行的剩余空间，我们会在当前行的词之间插入空格。因此，当前行中的空间取决于可能进入下一行或上一行的单词。这就是依赖!

你是暴力破解，你有依赖性，DP 来了!

现在让我们定义一个状态来确定我们解决这个问题的路径上的位置。

State:[i : j]，表示输入的原始单词序列中从第 i 个单词到第 j 个单词的单词行。

现在，您有了问题的状态，让我们尝试定义这些状态是如何相关的。

由于我们所有的子问题状态只是一堆单词，我们不能只比较每个状态中的单词并确定哪个更好。这里更好描述了使用行的宽度来保持特定行中单词之间的最大字符和最小空格。因此，我们定义了一个参数，它将衡量从第 i 个到第 j 个单词的单词列表的好坏程度。 (回想一下我们对子问题状态的定义)。这基本上是在评估我们的每个子问题状态。

一个简单的比较因素是:

定义 badness(i, j) 为 line of words[i : j]。

例如，如果总长度 > 页面宽度，则无穷大，else (页宽-当前行字数总和)3

为了使事情变得更简单，只考虑给定文本的后缀并应用此算法。这会将 DP 表大小从 N*N 减少到 N。

所以，为了完成，让我们用 DP 术语明确我们想要什么，

1. 子问题 = 最小。后缀词的坏处[i :]

   =⇒ 子问题数量 = Θ(n) 其中 n = 单词数量

2. guessing = 第一行在哪里结束，比如 i : j

   =⇒ 没有。 j = n − i = O(n) 的选择

3. 子问题之间的递归关系:

   • DP[i] = min(badness (i, j) + DP[j] for j in range (i + 1, n + 1))• DP[n] = 0

=⇒ 每个子问题的时间 = Θ(n)

因此，总时间 = Θ(n^2)。

另外，我会留给你如何在确定每行中的单词后在单词之间插入空格。