Description:
Given an array of strings 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 does 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
0and not exceedmaxWidth. - The input array
wordscontains at least one word.
Examples:
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 because 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 in Python:
Python
class Solution:
def fullJustify(self, words, maxWidth):
# Result list to hold the final output
result = []
# List to hold the current line's words
current_line = []
# Length of words in the current line without spaces
current_length = 0
for word in words:
# Check if adding the new word exceeds the maxWidth when considering spaces between words
if current_length + len(word) + len(current_line) > maxWidth:
# Time to justify the current line
for i in range(maxWidth - current_length):
# Distribute extra spaces as evenly as possible
# Use modulo to distribute spaces more to the left slots
current_line[i % (len(current_line) - 1 or 1)] += ' '
# Join the current line's words and add to the result
result.append(''.join(current_line))
# Reset current line and length for the next line
current_line, current_length = [], 0
# Add the word to the current line and update the length
current_line.append(word)
current_length += len(word)
# Handle the last line (left-justified)
result.append(' '.join(current_line).ljust(maxWidth))
return resultExplanation:
- Initialization:
result: A list to store the final lines.current_line: A list to hold words for the current line being processed.current_length: An integer to track the total length of words incurrent_linewithout considering spaces.
- Processing Words:
- Loop through each word in
words. - For each word, check if adding this word to
current_linewill exceedmaxWidth. The check considers the total length of words incurrent_line, the number of spaces needed between words (len(current_line)), and the length of the new word. - If it exceeds, the current line is full and needs to be justified:
- Distribute the extra spaces across the current line. This is done by adding a space to each slot in a round-robin fashion until all extra spaces are distributed. The
i % (len(current_line) - 1 or 1)ensures even distribution and handles the edge case where there is only one word in the line. - Join the words in
current_linewith spaces and add the justified line toresult. - Reset
current_lineandcurrent_lengthfor the next line.
- Distribute the extra spaces across the current line. This is done by adding a space to each slot in a round-robin fashion until all extra spaces are distributed. The
- If it doesn’t exceed, add the word to
current_lineand updatecurrent_length.
- Loop through each word in
- Last Line Handling:
- After processing all words, the last line in
current_lineis handled separately. It should be left-justified, which means words are joined with a single space, and the line is padded with spaces tomaxWidth.
- After processing all words, the last line in
This function ensures that each line meets the formatting requirements and distributes spaces as evenly as possible.
Solution in Javascript:
JavaScript
/**
* @param {string[]} words
* @param {number} maxWidth
* @return {string[]}
*/
var fullJustify = function(words, maxWidth) {
// Result array to hold the final output
let result = [];
// Array to hold the current line's words
let currentLine = [];
// Length of words in the current line without spaces
let currentLength = 0;
for (let word of words) {
// Check if adding the new word exceeds the maxWidth when considering spaces between words
if (currentLength + word.length + currentLine.length > maxWidth) {
// Time to justify the current line
for (let i = 0; i < maxWidth - currentLength; i++) {
// Distribute extra spaces as evenly as possible
// Use modulo to distribute spaces more to the left slots
currentLine[i % (currentLine.length - 1 || 1)] += ' ';
}
// Join the current line's words and add to the result
result.push(currentLine.join(''));
// Reset current line and length for the next line
currentLine = [];
currentLength = 0;
}
// Add the word to the current line and update the length
currentLine.push(word);
currentLength += word.length;
}
// Handle the last line (left-justified)
result.push(currentLine.join(' ').padEnd(maxWidth));
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
// Result list to hold the final output
List<String> result = new ArrayList<>();
// List to hold the current line's words
List<String> currentLine = new ArrayList<>();
// Length of words in the current line without spaces
int currentLength = 0;
for (String word : words) {
// Check if adding the new word exceeds the maxWidth when considering spaces between words
if (currentLength + word.length() + currentLine.size() > maxWidth) {
// Time to justify the current line
int spacesNeeded = maxWidth - currentLength;
int gaps = currentLine.size() - 1;
if (gaps == 0) {
// Special case for a line with only one word
currentLine.set(0, currentLine.get(0) + " ".repeat(spacesNeeded));
} else {
for (int i = 0; i < spacesNeeded; i++) {
// Distribute extra spaces as evenly as possible
// Use modulo to distribute spaces more to the left slots
currentLine.set(i % gaps, currentLine.get(i % gaps) + " ");
}
}
// Join the current line's words and add to the result
result.add(String.join("", currentLine));
// Reset current line and length for the next line
currentLine.clear();
currentLength = 0;
}
// Add the word to the current line and update the length
currentLine.add(word);
currentLength += word.length();
}
// Handle the last line (left-justified)
String lastLine = String.join(" ", currentLine);
result.add(lastLine + " ".repeat(maxWidth - lastLine.length()));
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
using System.Text;
public class Solution {
public IList<string> FullJustify(string[] words, int maxWidth) {
// Result list to hold the final output
IList<string> result = new List<string>();
// List to hold the current line's words
List<string> currentLine = new List<string>();
// Length of words in the current line without spaces
int currentLength = 0;
foreach (string word in words) {
// Check if adding the new word exceeds the maxWidth when considering spaces between words
if (currentLength + word.Length + currentLine.Count > maxWidth) {
// Time to justify the current line
int spacesNeeded = maxWidth - currentLength;
int gaps = currentLine.Count - 1;
if (gaps == 0) {
// Special case for a line with only one word
currentLine[0] = currentLine[0].PadRight(maxWidth);
} else {
for (int i = 0; i < spacesNeeded; i++) {
// Distribute extra spaces as evenly as possible
// Use modulo to distribute spaces more to the left slots
currentLine[i % gaps] += " ";
}
}
// Join the current line's words and add to the result
result.Add(string.Join("", currentLine));
// Reset current line and length for the next line
currentLine.Clear();
currentLength = 0;
}
// Add the word to the current line and update the length
currentLine.Add(word);
currentLength += word.Length;
}
// Handle the last line (left-justified)
StringBuilder lastLine = new StringBuilder(string.Join(" ", currentLine));
lastLine.Append(' ', maxWidth - lastLine.Length);
result.Add(lastLine.ToString());
return result;
}
}