leetcode: Text Justification

问题描述：

Given an array of words and a length L, format the text such that each line has exactly L 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 Lcharacters.

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.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

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

 

Note: Each word is guaranteed not to exceed L in length.

click to show corner cases.

 

Corner Cases:

 

• A line other than the last line might contain only one word. What should you do in this case?
• In this case, that line should be left-justified.

 

原问题链接：https://leetcode.com/problems/text-justification/

 

问题分析

　　这个问题其实本身的逻辑不算很复杂，主要是各种处理很麻烦，比较费事。总的来说，可以这么来看。这边要求是每一行放若干个词，但是词和词之间的空格尽可能的均匀。从最基本的要求来看，就有这么几个步骤。首先，要计算确定每一行可以放多少个词，保证它们不超过指定的长度。同时，在判断出最多可以放多少个词之后要计算里面有多少个空格，再将这些空格平均的放到所有这些词之间。最后，针对最后的一行，将剩下的词按照左对齐的方式来排版。我们针对这每个步骤的详细实现来讨论。

　　首先看判断一行里可以放多少个词。我们可以用一个变量minL来记录在某一行里放置的单词的总长度。同时用s来表示当前行开始的词的索引。首先它放置第一个词的长度。然后我们每次尝试往里面放一个后面的词并判断它们的长度是否超过限定的长度。当超过给定长度的时候，我们要将当前minL的长度减去当前位置的这个字符串的长度。

这部分的代码实现如下：

int s = 0; // line starting index in words
int n = words.length;
int minL = words[s].length(); // min length needed for the words
int e = s + 1;
// first figure out how many words can fit in the line
while (e < n) {
    minL += 1 + words[e].length();
    if (minL > maxWidth) {
        minL -= 1 + words[e].length(); // keep minL valid
        break;
    }
    ++e;
} // index e is exclusive

　　在上述的实现里我们需要注意一个地方。每次我们往minL里加词长度的时候要额外加１，这里的1是表示每个词后面所带的空格。因为我们最少要保证词和词之间有一个空格。这样，在索引e - 1到s这一段就是我们找到的放在给定maxWidth长度行里的词。 

　　有了上面这部分的实现，我们相当于找到了一种最初始的一个词加一个空格排列的情况。但是因为这种方式不一定和给定的maxWidth完全对齐的，有可能后面有多余的空格。我们需要针对这些空格的数量进行一个总体的分配。所以这一步就是要计算并放置一行里字符串和对应的空格。

　　这部分的实现该怎么来考虑呢？首先，根据当前e和s的值可以知道里面有多少个词加空格。它的值是e - s - 1。另外，根据maxWidth - minL得到的剩余空格数也要考虑在内。用这个剩余的空格数除以所有放词加空格的数量，作为平均放到每个块里的空格补充。详细的实现如下：

 

StringBuilder sb = new StringBuilder();
sb.append(words[s]); // append the 1st word
int slots = e - s - 1; // how many slots can be filled with spaces
int extra = maxWidth - minL; // total extra spaces need to be distributed
while (slots > 0) {
    // caculates how many extra spaces the current slot needs to take
    // it is the ceiling of (extra / slots)
    // in case of last line, 0
    int spaces = n == e ? 0 : ((extra + slots - 1) / slots);
    for (int i = 0; i <= spaces; ++i) sb.append(' '); // append those spaces, plus one
    sb.append(words[e-slots]); // append next word
    --slots; // one less slot to worry about
    extra -= spaces; // reduce the number of extra spaces filled this time
}
// fill the rest of the extra space to cover the one word and the last line case
for (int i = 0; i < extra; ++i) sb.append(' ');
res.add(sb.toString());

　　上述的过程描述的其实是针对一行字符串填充和选择的情况。针对将所有字符串按照给定样式排版的情况，需要将上述的代码嵌套到一个循环里。 

　　最后详细的代码实现如下：

 

public class Solution {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int s = 0; // line starting index in words
        int n = words.length;
        while (s < n) {
            int minL = words[s].length(); // min length needed for the words
            int e = s+1;
            // first figure out how many words can fit in the line
            while (e < n) {
                minL += 1 + words[e].length();
                if (minL > maxWidth) {
                    minL -= 1 + words[e].length(); // keep minL valid
                    break;
                }
                ++e;
            } // index e is exclusive
            StringBuilder sb = new StringBuilder();
            sb.append(words[s]); // append the 1st word
            int slots = e - s - 1; // how many slots can be filled with spaces
            int extra = maxWidth - minL; // total extra spaces need to be distributed
            while (slots > 0) {
                // caculates how many extra spaces the current slot needs to take
                // it is the ceiling of (extra / slots)
                // in case of last line, 0
                int spaces = n == e ? 0 : ((extra + slots - 1) / slots);
                for (int i = 0; i <= spaces; ++i) sb.append(' '); // append those spaces, plus one
                sb.append(words[e-slots]); // append next word
                --slots; // one less slot to worry about
                extra -= spaces; // reduce the number of extra spaces filled this time
            }
            // fill the rest of the extra space to cover the one word and the last line case
            for (int i = 0; i < extra; ++i) sb.append(' ');
            res.add(sb.toString());
            s = e; // move on
        }
        return res;
    }
}