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
wordscontains 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 " ]
class Solution { public List<String> fullJustify(String[] words, int maxWidth) { List<String> res = new ArrayList(); int left = 0; while(left < words.length) { int right = curright(left, words, maxWidth); res.add(justify(left, right, words, maxWidth)); left = right + 1; } return res; } public int curright(int left, String[] words, int maxWidth) { int right = left; int curlen = words[right++].length(); while(right < words.length && (curlen + 1 + words[right].length()) <= maxWidth) { curlen += 1 + words[right].length(); right++; } return right - 1; } public String justify(int left, int right, String[] words, int maxWidth) { if(left == right) return pad(words[left], maxWidth); boolean islastline = false; if(right == words.length - 1) islastline = true; StringBuilder sb = new StringBuilder(); int totalspaces = maxWidth - curline(left, right, words); String spaces = islastline ? " " : blank(totalspaces / (right - left)); int remains = islastline ? 0 : totalspaces % (right - left); for(int i = left; i < right; i++) { sb.append(words[i]). append(spaces). append( remains-- > 0 ? " " : ""); } sb.append(words[right]); if(islastline) return pad(sb.toString().trim(), maxWidth); return sb.toString(); } public String pad(String result, int maxWidth) { return result + blank(maxWidth - result.length()); } public int curline(int left, int right, String[] words) { int res = 0; for(int i = left; i <= right; i++) { res += words[i].length(); } return res; } public String blank(int length) { return new String(new char[length]).replace(' ', ' '); } }
大体上来说不是很难（才怪，主要是要把这些逻辑实现了要考虑到很多边边角角。
题目的意思是说给了一组string，按如下方式分行存到list中：
一行最多只能有maxWidth个char，
要尽可能多的放入words，两个word之间至少有1个space，最多的情况要进行计算，大体上来说要evenly distribute，如果无法实现，就先往左边的空格里面加剩下的space（每个只能加一个space保证evenly）
最后一行相邻word间只能有一个空格，剩余全是空格。
总结：
So how do we start this question? Firstly, we know we should add string line by line, so we wonder what is the start and end index in the array?
Starting form 0, we used a method curright() to get the right boundry of , by checking the validity of right index and curlength + 1(space) + word[right] <= maxWidth.
Then we use justify() to generate the string of current line, there are several situations,
1. left == right, this is the situation in last line and only ONE word left, so we directly add the padded result of (words[left]).
2. create a variable islastline to check if it is in the last line, by checking right == words.length - 1 ?
3. If not, we calculated all spaces we need in current line by maxWidth - curline(), which is the total chars number of current line. Then calculate how many spaces each word should append, by totalspaces / (right - left),
then the remaining is totalspaces % (right - left).
4. From left to right we append each word, some spaces, and remained spaces if any.
5. We saw that only the last line need to be padded, then we return the the current line's string.