Problem Statement: Text Justification
You are given a list of words and a length maxWidth. Your task is to arrange the words in such a way that the text is fully justified. The goal is to make each line of text exactly maxWidth characters long.
The rules for text justification are:
- Words are separated by exactly one space.
- Extra spaces are added between words to fill the line up to
maxWidth. - For a line with multiple words, spaces should be distributed as evenly as possible. If the spaces cannot be evenly distributed, the extra spaces should be distributed from left to right.
Example:
Input:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Approach:
To solve this problem, we need to build the lines word by word, ensuring that each line is fully justified. Here’s how we can do it step by step:
- Group Words into Lines:
- Iterate through the list of words and keep adding them to the current line until adding another word would exceed
maxWidth. - Once the line is filled, move to the next line.
- Iterate through the list of words and keep adding them to the current line until adding another word would exceed
- Justify Each Line:
- For lines that contain more than one word, calculate the number of spaces to distribute.
- Evenly distribute the spaces between the words.
- If the spaces don’t divide evenly, place the extra spaces from left to right.
- Last Line Special Case:
- The last line of text is left-justified. Spaces between words should be one, and any remaining spaces should be added at the end of the line.
Algorithm:
- Traverse through the
wordslist and group them into lines such that the total length of the words plus the spaces between them does not exceedmaxWidth. - For each line (except the last one), distribute spaces evenly between words.
- For the last line, left justify the words and add any remaining spaces to the right end.
Time Complexity:
- O(n) where
nis the number of words. We process each word exactly once. - O(n) for building and formatting the result strings.
Space Complexity:
- O(n) for storing the result.
Code Implementations:
1. C
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
char** fullJustify(char** words, int wordsSize, int maxWidth, int* returnSize) {
// Initialize return array
char** result = (char**)malloc(sizeof(char*) * wordsSize);
*returnSize = 0;
int i = 0;
while (i < wordsSize) {
int j = i + 1;
int lineLength = strlen(words[i]);
// Add words to the current line
while (j < wordsSize && lineLength + strlen(words[j]) + (j - i - 1) < maxWidth) {
lineLength += strlen(words[j]);
j++;
}
// Now we have words[i...j-1] in the current line
int numWords = j - i;
int numSpaces = maxWidth - lineLength;
char* line = (char*)malloc(sizeof(char) * (maxWidth + 1));
int pos = 0;
// If it's a single word, just copy it
if (numWords == 1) {
strcpy(line, words[i]);
pos += strlen(words[i]);
while (pos < maxWidth) {
line[pos++] = ' ';
}
} else {
// Distribute spaces
int evenSpace = numSpaces / (numWords - 1);
int extraSpace = numSpaces % (numWords - 1);
for (int k = i; k < j - 1; k++) {
strcpy(&line[pos], words[k]);
pos += strlen(words[k]);
for (int s = 0; s < evenSpace; s++) {
line[pos++] = ' ';
}
if (extraSpace > 0) {
line[pos++] = ' ';
extraSpace--;
}
}
strcpy(&line[pos], words[j - 1]);
pos += strlen(words[j - 1]);
}
line[pos] = '\0';
result[*returnSize] = line;
(*returnSize)++;
i = j;
}
return result;
}
int main() {
char* words[] = {"This", "is", "an", "example", "of", "text", "justification."};
int wordsSize = 7;
int maxWidth = 16;
int returnSize = 0;
char** result = fullJustify(words, wordsSize, maxWidth, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("\"%s\"\n", result[i]);
free(result[i]);
}
free(result);
return 0;
}
2. C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<string> fullJustify(vector<string>& words, int maxWidth) {
vector<string> result;
int n = words.size();
int i = 0;
while (i < n) {
int length = words[i].size();
int j = i + 1;
// Fit as many words as possible in the current line
while (j < n && length + words[j].size() + (j - i - 1) < maxWidth) {
length += words[j].size();
j++;
}
int numWords = j - i;
int numSpaces = maxWidth - length;
string line = "";
// Single word case
if (numWords == 1) {
line = words[i];
while (line.size() < maxWidth) {
line += " ";
}
} else {
int spacesPerGap = numSpaces / (numWords - 1);
int extraSpaces = numSpaces % (numWords - 1);
for (int k = i; k < j - 1; k++) {
line += words[k];
line += string(spacesPerGap, ' ');
if (extraSpaces-- > 0) line += " ";
}
line += words[j - 1];
}
result.push_back(line);
i = j;
}
return result;
}
int main() {
vector<string> words = {"This", "is", "an", "example", "of", "text", "justification."};
int maxWidth = 16;
vector<string> result = fullJustify(words, maxWidth);
for (const string& line : result) {
cout << "\"" << line << "\"" << endl;
}
return 0;
}
3. Java
import java.util.*;
public class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> result = new ArrayList<>();
int n = words.length;
int i = 0;
while (i < n) {
int length = words[i].length();
int j = i + 1;
// Fit as many words as possible in the current line
while (j < n && length + words[j].length() + (j - i - 1) < maxWidth) {
length += words[j].length();
j++;
}
int numWords = j - i;
int numSpaces = maxWidth - length;
StringBuilder line = new StringBuilder();
// Single word case
if (numWords == 1) {
line.append(words[i]);
while (line.length() < maxWidth) {
line.append(" ");
}
} else {
int spacesPerGap = numSpaces / (numWords - 1);
int extraSpaces = numSpaces % (numWords - 1);
for (int k = i; k < j - 1; k++) {
line.append(words[k]);
for (int s = 0; s < spacesPerGap; s++) {
line.append(" ");
}
if (extraSpaces > 0) {
line.append(" ");
extraSpaces--;
}
}
line.append(words[j - 1]);
}
result.add(line.toString());
i = j;
}
return result;
}
public static void main(String[] args) {
Solution solution = new Solution();
String[] words = {"This", "is", "an", "example", "of", "text", "justification."};
int maxWidth = 16;
List<String> result = solution.fullJustify(words, maxWidth);
for (String line : result) {
System.out.println("\"" + line + "\"");
}
}
}
4. Python
def fullJustify(words, maxWidth):
result = []
i = 0
while i < len(words):
line_length = len(words[i])
j = i + 1
# Add words to the current line until the width is exceeded
while j < len(words) and line_length + len(words[j]) + (j - i - 1) < maxWidth:
line_length += len(words[j])
j += 1
# Calculate spaces
num_words = j - i
num_spaces = maxWidth - line_length
line = ""
# Single word case
if num_words == 1:
line = words[i]
while len(line) < maxWidth:
line += " "
else:
spaces_per_gap = num_spaces // (num_words - 1)
extra_spaces = num_spaces % (num_words - 1)
for k in range(i, j - 1):
line += words[k]
line += " " * spaces_per_gap
if extra_spaces > 0:
line += " "
extra_spaces -= 1
line += words[j - 1]
result.append(line)
i = j
return result
# Test
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
result = fullJustify(words, maxWidth)
for line in result:
print(f"\"{line}\"")
5. C#
using System;
using System.Collections.Generic;
using System.Text;
class Solution {
public IList<string> FullJustify(string[] words, int maxWidth) {
List<string> result = new List<string>();
int n = words.Length;
int i = 0;
while (i < n) {
int length = words[i].Length;
int j = i + 1;
// Add words to the current line until the width is exceeded
while (j < n && length + words[j].Length + (j - i - 1) < maxWidth) {
length += words[j].Length;
j++;
}
int numWords = j - i;
int numSpaces = maxWidth - length;
StringBuilder line = new StringBuilder();
// Single word case
if (numWords == 1) {
line.Append(words[i]);
while (line.Length < maxWidth) {
line.Append(" ");
}
} else {
int spacesPerGap = numSpaces / (numWords - 1);
int extraSpaces = numSpaces % (numWords - 1);
for (int k = i; k < j - 1; k++) {
line.Append(words[k]);
for (int s = 0; s < spacesPerGap; s++) {
line.Append(" ");
}
if (extraSpaces > 0) {
line.Append(" ");
extraSpaces--;
}
}
line.Append(words[j - 1]);
}
result.Add(line.ToString());
i = j;
}
return result;
}
public static void Main() {
Solution sol = new Solution();
string[] words = { "This", "is", "an", "example", "of", "text", "justification." };
int maxWidth = 16;
IList<string> result = sol.FullJustify(words, maxWidth);
foreach (var line in result) {
Console.WriteLine($"\"{line}\"");
}
}
}
6. JavaScript
function fullJustify(words, maxWidth) {
let result = [];
let i = 0;
while (i < words.length) {
let lineLength = words[i].length;
let j = i + 1;
// Add words to the current line until the width is exceeded
while (j < words.length && lineLength + words[j].length + (j - i - 1) < maxWidth) {
lineLength += words[j].length;
j++;
}
// Calculate spaces
let numWords = j - i;
let numSpaces = maxWidth - lineLength;
let line = "";
// Single word case
if (numWords === 1) {
line = words[i];
while (line.length < maxWidth) {
line += " ";
}
} else {
let spacesPerGap = Math.floor(numSpaces / (numWords - 1));
let extraSpaces = numSpaces % (numWords - 1);
for (let k = i; k < j - 1; k++) {
line += words[k];
line += " ".repeat(spacesPerGap);
if (extraSpaces > 0) {
line += " ";
extraSpaces--;
}
}
line += words[j - 1];
}
result.push(line);
i = j;
}
return result;
}
// Test
let words = ["This", "is", "an", "example", "of", "text", "justification."];
let maxWidth = 16;
let result = fullJustify(words, maxWidth);
for (let line of result) {
console.log(`"${line}"`);
}
Summary:
The solution takes into account various edge cases like:
- Single word in a line.
- Correct space distribution when multiple words are present.
- Proper formatting for the last line (left-justified).
The time complexity is O(n) because each word is processed once, and the space complexity is also O(n) due to storing the result.