Sponsored
Sponsored
This approach involves iterating through the given words and greedily forming a line by adding as many words as possible without exceeding the maxWidth. When a line is completed, the algorithm distributes spaces evenly between words. If the number of spaces doesn’t divide evenly, more spaces are added to the left slots. The last line is treated differently by left-justifying the text.
Time Complexity: O(n), where n is the total number of characters in all words.
Space Complexity: O(n), where n is the number of lines formed times maxWidth for the justified text.
1function fullJustify(words, maxWidth) {
2 const result = [];
3 let idx = 0;
4 const justify = (line, maxWidth, isLastLine) => {
5 if (line.length === 1) return line[0].padEnd(maxWidth);
6 if (isLastLine) return line.join(' ').padEnd(maxWidth);
7 const totalSpace = maxWidth - line.join('').length;
8 const gaps = line.length - 1;
9 const spaceBetween = Math.floor(totalSpace / gaps);
10 const extraSpaces = totalSpace % gaps;
11 return line.reduce((acc, word, i) => {
12 if (i === gaps) return acc + word;
13 return acc + word + ' '.repeat(spaceBetween + (i < extraSpaces ? 1 : 0));
14 }, '');
15 };
16
17 while (idx < words.length) {
18 let line = [];
19 let lineLength = 0;
20 while (idx < words.length && lineLength + words[idx].length + line.length <= maxWidth) {
21 lineLength += words[idx].length;
22 line.push(words[idx++]);
23 }
24 result.push(justify(line, maxWidth, idx === words.length));
25 }
26 return result;
27}This JavaScript implementation utilizes a justify helper function to handle spaces distribution. It iterates words, grouping them greedily into a line. When a line's length plus planned spaces exceed maxWidth, it's justified appropriately depending on whether it's the last line or not. Spaces are distributed evenly among words between gaps.
This method leverages dynamic programming to minimize a hypothetical cost function that combines badness or uneven space distribution along with total number of lines used, aiming to determine the optimal setup of words per line.
Time Complexity: O(n^2), due to potential double iterations required for exploring word positions.
Space Complexity: O(n), since it uses extra space for storing dp and path arrays.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <climits>
5using namespace std;
vector<string> fullJustify(vector<string>& words, int maxWidth) {
int n = words.size();
vector<int> dp(n + 1, INT_MAX);
vector<int> path(n);
dp[n] = 0;
for (int i = n - 1; i >= 0; --i) {
int len = -1;
for (int j = i; j < n; ++j) {
len += words[j].length() + 1;
if (len > maxWidth) break;
int last_cost = j == n - 1 ? 0 : maxWidth - len;
if (dp[i] > last_cost + dp[j + 1]) {
dp[i] = last_cost + dp[j + 1];
path[i] = j + 1;
}
}
}
vector<string> res;
for (int i = 0; i < n; i = path[i]) {
int j = path[i];
string line = words[i];
for (int k = i + 1; k < j; ++k) {
line += " " + words[k];
}
line += string(maxWidth - line.length(), ' ');
res.push_back(line);
}
return res;
}This C++ implementation uses a dynamic programming table, dp, to compute the minimum penalty of breaking words into lines. path is used to store optimal partitioning. The final step reconstructs justified text using information stored in path.