最近我在一次面试中被要求设计一种算法，将左对齐（每行末尾有空格）的输入字符串转换为对齐（整行末尾没有空格），类似于在 MS Word 中。 我向他提出了一些基本的解决方案，其中包括计算每行的单词数和空格数，然后将它们平均分配到所有空格中（他要求我假设分数空格可以在单词之间分配）。但后来他让我考虑整个段落，然后修改文本，以便在单词之间的空格分布不均不可避免时不失去文本的美感。
当时我无法想到任何合适的解决方案。后来他告诉我这是动态规划完成的。 我不确定是否已经有一些标准算法。如果是，请分享一些有用的链接。
PS：我提出的解决方案是非常抽象的想法，因此我没有任何代码来显示我已经尝试过的所有内容。 理由：http://en.wikipedia.org/wiki/Justification_（排版）
将段落分成行的标准算法可能仍然是 Knuth & Plass 的算法，由 Knuth 的排版系统使用
TeXDonald E. Knuth 和 Michael F. Plass，软件 - 实践和经验 11 (1981) 1119-1184 DOI：10.1002/spe.4380111102， 也可在数字排版，第 1 章中找到。 3，第 67–155 页。
该算法基于考虑每个可能的换行符，开始 从段落的开头开始，对于每一个发现 给出最佳结果的前面换行符的顺序 这么远。由于整个序列是由最后一个换行符决定的 在序列中，只有当前的潜在起点 当要设置新的潜在断点时，必须考虑线路 添加，从而产生有效的算法。
该算法的简化版本（没有 e.g. 连字符），可以 可以这样描述：
Add start of paragraph to list of active breakpoints
For each possible breakpoint (space) B_n, starting from the beginning:
For each breakpoint in active list as B_a:
If B_a is too far away from B_n:
Delete B_a from active list
else
Calculate badness of line from B_a to B_n
Add B_n to active list
If using B_a minimizes cumulative badness from start to B_n:
Record B_a and cumulative badness as best path to B_n
The result is a linked list of breakpoints to use.
The badness of lines under consideration can be calculated like this:
Each space is assigned a nominal width, a strechability, and a shrinkability.
The badness is then calculated as the ratio of stretching or shrinking used,
relative to what is allowed, raised e.g. to the third power (in order to
ensure that several slightly bad lines are prefered over one really bad one)
可在以下位置找到图解说明： http://defoe.sourceforge.net/folio/knuth-plass.html
网络上提供了各种语言的实现，例如 Bram Stein 在 Javascript 中的实现：http://www.bramstein.com/projects/typeset/
我做了一个空格插入器功能:)
但是只需插入一个空格，直到线宽小于所需的宽度即可。
public static List<string> GetText(string text, int width)
{
string[] palabras = text.Split(' ');
StringBuilder sb1 = new StringBuilder();
StringBuilder sb2 = new StringBuilder();
int length = palabras.Length;
List<string> resultado = new List<string>();
for (int i = 0; i < length; i++)
{
sb1.AppendFormat("{0} ", palabras[i]);
if (sb1.ToString().Length > width)
{
resultado.Add(sb2.ToString());
sb1 = new StringBuilder();
sb2 = new StringBuilder();
sb1.AppendFormat("{0} ", palabras[i]);
}
else
{
sb2.AppendFormat("{0} ", palabras[i]);
}
}
resultado.Add(sb2.ToString());
List<string> resultado2 = new List<string>();
string temp;
int index1, index2, salto;
string target;
int limite = resultado.Count;
foreach (var item in resultado)
{
target = " ";
temp = item.ToString().Trim();
index1 = 0; index2 = 0; salto = 2;
if (limite <= 1)
{
resultado2.Add(temp);
break;
}
while (temp.Length <= width)
{
if (temp.IndexOf(target, index2) < 0)
{
index1 = 0; index2 = 0;
target = target + " ";
salto++;
}
index1 = temp.IndexOf(target, index2);
temp = temp.Insert(temp.IndexOf(target, index2), " ");
index2 = index1 + salto;
}
limite--;
resultado2.Add(temp);
}
return resultado2;
}
希望有帮助！
我建议任何想要详细了解这个问题的来龙去脉的人，观看 MIT 6.006 课程 - 第 20 号讲座
这是它的链接。
我需要做类似的事情，以便找到最统一的方式来分割线条，并添加可能存在不可见标记标签的皱纹。
这个问题最终比我最初想象的更有趣。 我使用递归来围绕单词边界创建可能的布局。 然后对布局进行排序以找到最好的布局。