题目
给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。
注意:
单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。
解题思路
- 模拟：考虑模拟一行一行的放置单词,主要处理每行放多少单词以及两端对齐时空格数量的计算,注释代码如下所示。
模拟 0ms
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
//考虑模拟一行一行的放
List<String> ans = new ArrayList<>();
int wordIndex = 0;
while(wordIndex < words.length) {
int count = 1,len = words[wordIndex].length();
for(int i = wordIndex + 1; i < words.length; i++) {
if(len + 1 + words[i].length() > maxWidth) break;
len += 1 + words[i].length();
count ++;
}
StringBuilder sb = new StringBuilder();
if(count == 1) { //只有一个单词
sb.append(words[wordIndex]);
//补空格
for(int i = 0; i < maxWidth - words[wordIndex].length(); i++)
sb.append(' ');
} else if(wordIndex + count == words.length || maxWidth == len) {
//最后一行 或者刚好间隔一个空格
for(int i = 0; i < count; i++) {
if(sb.length() > 0) sb.append(' ');
sb.append(words[wordIndex + i]);
}
//补空格
for(int i = 0,sbLen = sb.length(); i < maxWidth - sbLen; i++)
sb.append(' ');
}else { //两边对齐
//计算空格长度
int spaceLen = (maxWidth - len + count - 1)/(count - 1);
int leftSpace = maxWidth - len + count - 1 - (count - 1) * spaceLen;
StringBuilder spaces = new StringBuilder(spaceLen);
for(int i = 0; i < spaceLen; i++)
spaces.append(' ');
for(int i = 0; i < count; i++) {
if(sb.length() > 0){
sb.append(spaces); //插入空格 和多余空格
if(leftSpace-- > 0) sb.append(' ');
}
sb.append(words[wordIndex + i]);
}
}
ans.add(sb.toString());
wordIndex += count;
}
return ans;
}
}
复杂度分析
- 时间复杂度：
O(n)，n为所有单词长度之和。 - 空间复杂度：
O(k)，k为StringBuilder使用空间maxWidth。
