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 "
]
Solution
什么时候该换行
由于一行的最大字符数量为 L ，并且在两个单词之间必须有至少一个空格的间隔。也就是说在最紧凑的情况下，N 个单词需要占的字符数量为这 N 个单词的字符总数加上 N-1 个空格的长度。
因此可以通过扫描一遍数组，理清每一行是由哪些连续的字符组成，其代码如下：
int prev = 0; // 表示该行起点的位置
int len = -1; // 方便处理第一次计算
for (int i = 0; i < words.size(); ++i) {
if (len + 1 + words[i].size() <= maxWidth)
len += 1 + words[i].size(); // 在紧凑放置的情况下仍然不超过 L
else {
ret.push_back( getALine(words, maxWidth, prev, i - 1) ); // 处理prev到i-1这一行
// 新的一行
len = words[i].size();
prev = i;
}
}
如何处理一行
在我们已经知道该行单词的情况下，我们需要注意，这几个单词在紧凑情况下不一定能够达到 L 长度，所以我们需要对空格的数量进行分配。
- 根据题目要求，我们先要将空格尽可能平均分配到每两个单词之间，此时若仍然有额外的空格，需加在靠前的隔中。
int spaceCount = (maxWidth - totLen) / (end - start); // 每个间隔之间的空格数
int extraCount = (maxWidth - totLen) % (end - start); // 需要额外增加空格的间隔数
- 然后根据
spaceCount和extraCount我们可以得到一行的字符串：
if (wordEndIndex != words.length - 1) {
int evenSpaceCount = (maxWidth - allWordsLen) / (wordEndIndex - wordStartIndex);
int extraCount = (maxWidth - allWordsLen) % (wordEndIndex - wordStartIndex);
result = words[wordStartIndex];
for (int index = wordStartIndex + 1; index <= wordEndIndex; index++) {
for (int spaceIndex = 0; spaceIndex < evenSpaceCount; spaceIndex++) {
result += " ";
}
if (extraCount -- > 0) {
result += " ";
}
result += words[index];
}
}
- 但是对于最后一行，题目要求左对齐，需特殊处理
else { //3. special handle the last line
result = words[wordStartIndex];
for (int index = wordStartIndex + 1; index <= wordEndIndex; index++) {
result += " ";
result += words[index];
}
for (int index = result.length (); index < maxWidth; index++) {
result += " ";
}
}
其他注意点
在处理的过程中，我们还需要注意：
-
当前行为最后一行时，不需要将间隔扩展使得最后一个单词末尾为行末。但是需要将末尾补足空格。
-
若一行只有1个单词时，需要将末尾补足空格
-
若给定的单词序列一个词都没有，仍然需要输出一个长度为 L 的空行。
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<> ();
if (words == null || words.length == 0) {
return result;
}
// to handle the first word
int wordLen = -1;
int wordStartIndex = 0;
// find words can put in a line and get the line
for (int i = 0; i < words.length; i++) {
// still can fit into a line
if (wordLen + 1 + words[i].length () <= maxWidth) {
wordLen += 1 + words[i].length ();
} else { // cannot fit into a line, need to add a new line
result.add (getALine (words, maxWidth, wordStartIndex, i - 1)); //word start Index, end index, which would generate the line
// initialize the new line
wordLen = words[i].length ();
wordStartIndex = i;
}
}
// the last word cannot be handled in the loop, needs to handle
result.add (getALine (words, maxWidth, wordStartIndex, words.length - 1));
return result;
}
// helper function
public String getALine (String[] words, int maxWidth, int wordStartIndex, int wordEndIndex) {
if (wordStartIndex > wordEndIndex) {
return "";
}
// only has one word
if (wordStartIndex == wordEndIndex) {
String result = words [wordStartIndex];
for (int index = words [wordStartIndex].length (); index < maxWidth; index++) {
result += " ";
}
return result;
}
//has multiple words
//1. calculate all words length in this line
int allWordsLen = 0;
for (int index = wordStartIndex; index <= wordEndIndex; index++) {
allWordsLen += words [index].length ();
}
//2. get space count between each word (not the last line)
String result = "";
if (wordEndIndex != words.length - 1) {
int evenSpaceCount = (maxWidth - allWordsLen) / (wordEndIndex - wordStartIndex);
int extraCount = (maxWidth - allWordsLen) % (wordEndIndex - wordStartIndex);
result = words[wordStartIndex];
for (int index = wordStartIndex + 1; index <= wordEndIndex; index++) {
for (int spaceIndex = 0; spaceIndex < evenSpaceCount; spaceIndex++) {
result += " ";
}
if (extraCount -- > 0) {
result += " ";
}
result += words[index];
}
} else { //3. special handle the last line
result = words[wordStartIndex];
for (int index = wordStartIndex + 1; index <= wordEndIndex; index++) {
result += " ";
result += words[index];
}
for (int index = result.length (); index < maxWidth; index++) {
result += " ";
}
}
return result;
}
}
网友评论