LeetCode 68 - Text Justification

作者 QIFAN 日期 2016-12-21
LeetCode 68 - Text Justification

原题链接:68. Text Justification


题目

给一个 String 数组 words ,和每行最大长度 maxLength。要求将这个数组按行分组,其中每行长度为 maxLength,且左右对齐。也就是说,除非改行只有一个单词,不然都应以单词开头,并以单词结尾,其中单词应该均匀分布,也就是每个单词间的空格数应该相等,若不能相等,则先去填充左边的。最后一行应左对齐,也就是单词间没有多余的空格,不足的字符全在最后以空格补上。结果以 List 形式返回。

举例
words: [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”]
L: 16.
返回:

[
"This is an",
"example of text",
"justification. "
]

思路

我用的是一种常规的思路,计算每加一个单词后的长度,如果超过要求,则撤销一步操作,开始计算单词间距。
平均每个单词间距 = 总剩余长度 / (单词个数 - 1)
剩余空格 = 总剩余长度 % (单词个数 - 1)

最后一行另外进行处理。

当然还要考虑一些特殊情况:

  1. 空集
  2. 规定长度比单词的长度还小
  3. 一行只有一个单词

时间复杂度 $O(n)$

代码:

public class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
if (words == null || words.length == 0) {
return result;
}
int length = 0;
int startWordIndex = 0;
String line;
int lineWordNum = 0; // 每行单词个数
for (int i = 0; i < words.length; i++) {
if (words[i].length() > maxWidth) {
result.add("");
return result;
}
length += words[i].length();
lineWordNum++;
if (length + lineWordNum - 1 <= maxWidth) {
continue;
} else {
line = makeLine(words, maxWidth, startWordIndex, i, length - words[i].length());
result.add(line);
length = words[i].length();
startWordIndex = i;
lineWordNum = 1;
}
}
line = makeLastLine(words, maxWidth, startWordIndex);
result.add(line);
return result;
}
public String makeLine(String[] words, int maxWidth, int startWordIndex, int endWordIndex, int currentLength) {
StringBuilder line = new StringBuilder();
int totalPadSpaceNum = maxWidth - currentLength;
int avgPadSpaceNum;
int modPadSpaceNum;
// 如果只有一个单词
if (endWordIndex - startWordIndex == 1) {
avgPadSpaceNum = totalPadSpaceNum;
modPadSpaceNum = 0;
} else {
avgPadSpaceNum = totalPadSpaceNum / (endWordIndex - startWordIndex - 1);
modPadSpaceNum = totalPadSpaceNum % (endWordIndex - startWordIndex - 1);
}
for (int i = startWordIndex; i < endWordIndex - 1; i++) {
line.append(words[i]);
if (modPadSpaceNum-- > 0) {
line.append(" ");
}
int temp = avgPadSpaceNum;
while (temp-- > 0) {
line.append(" ");
}
}
line.append(words[endWordIndex - 1]);
while (line.length() < maxWidth) {
line.append(" ");
}
return line.toString();
}
public String makeLastLine(String[] words, int maxWidth, int startWordIndex) {
StringBuilder line = new StringBuilder();
for (int i = startWordIndex; i < words.length; i++) {
line.append(words[i]);
if (line.length() < maxWidth) {
line.append(" ");
}
}
while (line.length() < maxWidth) {
line.append(" ");
}
return line.toString();
}
}