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 0 and not exceed maxWidth. The input array words contains 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 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 " ] Constraints: 1 <= words.length <= 300 1 <= words[i].length <= 20 words[i] consists of only English letters and symbols. 1 <= maxWidth <= 100 words[i].length <= maxWidth
Java Solution
You can solve this problem by iteratively adding words to lines while considering the justification rules. Here’s a Java solution for the given problem:
import java.util.ArrayList;
import java.util.List;
public class TextJustification {
public static List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
int start = 0;
while (start < words.length) {
int end = findEndIndex(words, start, maxWidth);
if (end == start) {
// Handle the case when a single word exceeds maxWidth
result.add(leftJustify(words, start, end, maxWidth));
} else if (end == words.length - 1) {
// Handle the last line (left-justified)
result.add(leftJustify(words, start, end, maxWidth));
} else {
// Handle other lines (fully justified)
result.add(fullJustify(words, start, end, maxWidth));
}
start = end + 1;
}
return result;
}
private static int findEndIndex(String[] words, int start, int maxWidth) {
int end = start;
int currentWidth = words[start].length();
while (end + 1 < words.length && currentWidth + words[end + 1].length() + 1 <= maxWidth) {
end++;
currentWidth += words[end].length() + 1;
}
return end;
}
private static String leftJustify(String[] words, int start, int end, int maxWidth) {
StringBuilder line = new StringBuilder(words[start]);
for (int i = start + 1; i <= end; i++) {
line.append(" ").append(words[i]);
}
int spacesToAdd = maxWidth - line.length();
line.append(" ".repeat(Math.max(0, spacesToAdd)));
return line.toString();
}
private static String fullJustify(String[] words, int start, int end, int maxWidth) {
int totalSpaces = maxWidth - wordsLength(words, start, end);
int wordsCount = end - start + 1;
StringBuilder line = new StringBuilder(words[start]);
int spacesBetweenWords = wordsCount == 1 ? totalSpaces : totalSpaces / (wordsCount - 1);
int extraSpaces = wordsCount == 1 ? 0 : totalSpaces % (wordsCount - 1);
for (int i = start + 1; i <= end; i++) {
int spaces = spacesBetweenWords + (extraSpaces-- > 0 ? 1 : 0);
line.append(" ".repeat(Math.max(0, spaces))).append(words[i]);
}
return line.toString();
}
private static int wordsLength(String[] words, int start, int end) {
int length = 0;
for (int i = start; i <= end; i++) {
length += words[i].length();
}
return length;
}
public static void main(String[] args) {
String[] words1 = {"This", "is", "an", "example", "of", "text", "justification."};
int maxWidth1 = 16;
System.out.println(fullJustify(words1, maxWidth1));
String[] words2 = {"What","must","be","acknowledgment","shall","be"};
int maxWidth2 = 16;
System.out.println(fullJustify(words2, maxWidth2));
String[] words3 = {"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
int maxWidth3 = 20;
System.out.println(fullJustify(words3, maxWidth3));
}
}
This Java code defines a fullJustify method to generate fully justified lines and a leftJustify method for left-justified lines. The findEndIndex method finds the end index for each line, and the main method demonstrates the usage with the provided test cases.
Python Solution
def full_justify(words, maxWidth):
result = []
start = 0
while start < len(words):
end = find_end_index(words, start, maxWidth)
if end == start:
# Handle the case when a single word exceeds maxWidth
result.append(left_justify(words, start, end, maxWidth))
elif end == len(words) - 1:
# Handle the last line (left-justified)
result.append(left_justify(words, start, end, maxWidth))
else:
# Handle other lines (fully justified)
result.append(full_justify_line(words, start, end, maxWidth))
start = end + 1
return result
def find_end_index(words, start, maxWidth):
end = start
current_width = len(words[start])
while end + 1 < len(words) and current_width + len(words[end + 1]) + 1 <= maxWidth:
end += 1
current_width += len(words[end]) + 1
return end
def left_justify(words, start, end, maxWidth):
line = ' '.join(words[start:end+1])
spaces_to_add = maxWidth - len(line)
line += ' ' * spaces_to_add
return line
def full_justify_line(words, start, end, maxWidth):
total_spaces = maxWidth - words_length(words, start, end)
words_count = end - start + 1
line = words[start]
spaces_between_words = total_spaces // (words_count - 1) if words_count > 1 else total_spaces
extra_spaces = total_spaces % (words_count - 1) if words_count > 1 else 0
for i in range(start + 1, end + 1):
spaces = spaces_between_words + (1 if extra_spaces > 0 else 0)
extra_spaces -= 1
line += ' ' * spaces + words[i]
return line
def words_length(words, start, end):
return sum(len(word) for word in words[start:end+1])
# Test cases
words1 = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth1 = 16
print(full_justify(words1, maxWidth1))
words2 = ["What","must","be","acknowledgment","shall","be"]
maxWidth2 = 16
print(full_justify(words2, maxWidth2))
words3 = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]
maxWidth3 = 20
print(full_justify(words3, maxWidth3))
This Python code defines functions full_justify, left_justify, and full_justify_line to generate the fully justified and left-justified lines. The find_end_index function finds the end index for each line, and the words_length function calculates the length of words in a given range. The provided test cases demonstrate its usage.