68.Text-Justification

68. Text Justification

题目地址

题目描述

Given an array of words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.
​
You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.
​
Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
​
For the last line of text, it should be left justified and no extra space is inserted between words.
​
Note:
A word is defined as a character sequence consisting of non-space characters only.
Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.
​
Example 1:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
​
Example 2:
Input:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be",
because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.
​
Example 3:
Input:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]

代码

Approach #1

public class Solution {
public List<String> fullJustify(String[] words, int L) {
List<String> lines = new ArrayList<String>();
​
int index = 0;
while (index < words.length) {
int len = words[index].length();
// 1. 计算每行最大的单词个数
int lastIdx = index + 1;
while (lastIdx < words.length) {
if (words[lastIdx].length() + len + 1 > L) break;
len += words[lastIdx].length() + 1;
lastIdx++;
}
​
StringBuilder builder = new StringBuilder();
int diff = lastIdx - index - 1;
// 2. 最后一行或者单行只有一个单词,都按作左对齐处理
// if last line or number of words in the line is 1, left-justified
if (lastIdx == words.length || diff == 0) {
for (int i = index; i < lastIdx; i++) {
builder.append(words[i] + " ");
}
builder.deleteCharAt(builder.length() - 1);
for (int i = builder.length(); i < L; i++) {
builder.append(" ");
}
}
// 3. 否则根据剩余空间,来计算每个单词间距
else {
// middle justified
int spaces = (L - len) / diff;
// remaining number of space which we should insert from left to right
int r = (L - len) % diff;
for (int i = index; i < lastIdx; i++) {
builder.append(words[i]);
if (i < lastIdx - 1) {
int total_space = (spaces + ((i - index) < r ? 1 : 0);
for (int j = 0; j <= total_space); j++) {
builder.append(" ");
}
}
}
}
lines.add(builder.toString());
index = lastIdx;
}
​
return lines;
}
}

Approach #2:

class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
int left = 0; List<String> result = new ArrayList<>();
​
while (left < words.length) {
int right = findRight(left, words, maxWidth);
result.add(justify(left, right, words, maxWidth));
left = right + 1;
}
​
return result;
}
​
private int findRight(int left, String[] words, int maxWidth) {
int right = left;
int sum = words[right++].length();
​
while (right < words.length && (sum + 1 + words[right].length()) <= maxWidth)
sum += 1 + words[right++].length();
​
return right - 1;
}
​
private String justify(int left, int right, String[] words, int maxWidth) {
if (right - left == 0) return padResult(words[left], maxWidth);
​
boolean isLastLine = right == words.length - 1;
int numSpaces = right - left;
int totalSpace = maxWidth - wordsLength(left, right, words);
​
String space = isLastLine ? " " : blank(totalSpace / numSpaces);
int remainder = isLastLine ? 0 : totalSpace % numSpaces;
​
StringBuilder result = new StringBuilder();
for (int i = left; i <= right; i++)
result.append(words[i])
.append(space)
.append(remainder-- > 0 ? " " : "");
​
return padResult(result.toString().trim(), maxWidth);
}
​
private int wordsLength(int left, int right, String[] words) {
int wordsLength = 0;
for (int i = left; i <= right; i++) wordsLength += words[i].length();
return wordsLength;
}
​
private String padResult(String result, int maxWidth) {
return result + blank(maxWidth - result.length());
}
​
private String blank(int length) {
return new String(new char[length]).replace('\0', ' ');
}
}