最近我在一次采访中被要求设计一种算法，将左对齐（每行末尾有空格）的输入字符串转换为 Justify（整行末尾没有空格），类似于微软字。我向他提出了一些基本的解决方案，其中包括计算每行的单词数和空格数，然后将它们平均分配到所有空格中（他让我假设分数空间可以在单词之间分布）。但后来他让我考虑整个段落，然后修改文本，这样当单词之间的空格分布不均不可避免时，文本的美感就不会丢失。
当时我想不出任何合适的解决方案。后来他告诉我这是通过动态编程完成的。我不确定是否已经有一些标准算法。如果是，请分享一些有用的链接。
PS：我提出的解决方案是非常抽象的想法，因此我没有任何代码来显示我已经尝试过的所有内容。理由：http://en.wikipedia.org/wiki/Justification_(排版)
将段落分成行的标准算法可能仍然是 Knuth 的排版系统使用的 Knuth & Plass 的算法TeX。该算法“通过明智地使用动态编程技术避免回溯”在
Donald E. Knuth 和 Michael F. Plass，软件 - 实践和经验11 (1981) 1119-1184 DOI：10.1002/spe.4380111102，也可在Digital Typography中找到，Ch。3，第 67-155 页。
该算法基于考虑每个可能的换行符，从段落的开头开始，并为每个换行符找到之前的换行符序列，以提供迄今为止最好的结果。由于整个序列由序列中的最后一个换行符确定，因此在添加新的潜在断点时，只需考虑当前行的潜在起点，从而产生有效的算法。
该算法的简化版本（例如没有连字符）可以这样描述：
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;
}
希望能帮助到你！