68. Text Justification
給定一個字符串數組 words 和一個寬度 maxWidth，格式化文本使每行正好有 maxWidth 個字符並且完全（左右）對齊。
你應該使用貪心算法來打包單詞；也就是說，在每行中儘量多地打包單詞。當必要時，用額外的空格 ' ' 來填充，使每行正好有 maxWidth 個字符。
單詞之間的額外空格應盡可能均勻地分佈。如果行中的空格數無法在單詞間均勻分佈，則左側的空白槽比右側的多。
對於最後一行文本，應該左對齊，並且單詞之間不插入額外的空格。
注意：單詞被定義為僅由非空格字符組成的字符序列。
保證每個單詞的長度大於 0 並且不超過 maxWidth。
輸入數組 words 至少包含一個單詞。
範例 1：
輸入：words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16 輸出：[ "This is an", "example of text", "justification. "]
Python
from typing import List
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
result = []
current_line = []
current_length = 0
for word in words:
# Check if adding the new word exceeds the maxWidth
if current_length + len(word) + len(current_line) > maxWidth:
# Distribute spaces evenly among the words in the current_line
for i in range(maxWidth - current_length):
current_line[i % (len(current_line) - 1 or 1)] += ' '
result.append(''.join(current_line))
current_line, current_length = [], 0
current_line.append(word)
current_length += len(word)
# Handle the last line (left-justified)
result.append(' '.join(current_line).ljust(maxWidth))
return result
16.73MB, 23ms
C++
#include <vector>
#include <string>
#include <sstream>
using namespace std;
class Solution {
public:
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
vector<string> current_line;
int current_length = 0;
for (const string& word : words) {
// Check if adding the new word exceeds the maxWidth
if (current_length + word.size() + current_line.size() > maxWidth) {
// Distribute spaces evenly among the words in the current_line
for (int i = 0; i < maxWidth - current_length; ++i) {
current_line[i % (current_line.size() - 1 ? current_line.size()
- 1 : 1)] += ' ';
}
// Join the current_line into a single string and add it to the result
result.push_back(join(current_line, ""));
current_line.clear();
current_length = 0;
}
// Add the current word to the line
current_line.push_back(word);
current_length += word.size();
}
// Handle the last line (left-justified)
result.push_back(join(current_line, " ").append(maxWidth - current_length -
(current_line.size() - 1), ' '));
return result;
}
private:
string join(const vector<string>& words, const string& delimiter) {
stringstream ss;
for (size_t i = 0; i < words.size(); ++i) {
if (i != 0) {
ss << delimiter;
}
ss << words[i];
}
return ss.str();
}
};
9.16MB, 0ms
Javascript
/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
var fullJustify = function(words, maxWidth) {
const result = [];
let currentLine = [];
let currentLength = 0;
for (const word of words) {
// Check if adding the new word exceeds the maxWidth
if (currentLength + word.length + currentLine.length > maxWidth) {
// Distribute spaces evenly among the words in the currentLine
for (let i = 0; i < maxWidth - currentLength; i++) {
currentLine[i % (currentLine.length - 1 || 1)] += ' ';
}
// Join the currentLine into a single string and add it to the result
result.push(currentLine.join(''));
currentLine = [];
currentLength = 0;
}
// Add the current word to the line
currentLine.push(word);
currentLength += word.length;
}
// Handle the last line (left-justified)
result.push(currentLine.join(' ') + ' '.repeat(maxWidth - currentLength -
(currentLine.length - 1)));
return result;
};
49.09MB, 52ms
