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.
1import java.util.*;
2
3public class TextJustification {
4 public List<String> fullJustify(String[] words, int maxWidth) {
5 List<String> result = new ArrayList<>();
6 int index = 0;
7 while (index < words.length) {
8 int totalChars = words[index].length();
9 int last = index + 1;
10 while (last < words.length) {
11 if (totalChars + words[last].length() + 1 > maxWidth) break;
12 totalChars += words[last].length() + 1;
13 last++;
14 }
15
16 StringBuilder sb = new StringBuilder();
17 int diff = last - index - 1;
18 // if last line or number of words in the line is 1, left-justify
19 if (last == words.length || diff == 0) {
20 for (int i = index; i < last; i++) {
21 sb.append(words[i]).append(" ");
22 }
23 sb.deleteCharAt(sb.length() - 1);
24 while (sb.length() < maxWidth) {
25 sb.append(" ");
26 }
27 } else {
28 int spaces = (maxWidth - totalChars) / diff;
29 int remainder = (maxWidth - totalChars) % diff;
30 for (int i = index; i < last - 1; i++) {
31 sb.append(words[i]).append(" ");
32 for (int j = 0; j < spaces + (i - index < remainder ? 1 : 0); j++) {
33 sb.append(" ");
34 }
35 }
36 sb.append(words[last - 1]);
37 }
38 result.add(sb.toString());
39 index = last;
40 }
41 return result;
42 }
43}This Java implementation uses a while loop to process words. It determines the range of words that can fit into the current line, then builds the line accordingly. It checks if it's the last line or if only one word exists in the line, in which case left-justification is applied. Otherwise, the spaces are evenly distributed.
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.
1using System;
2using System.Collections.Generic;
3using System.Text;
4
5public class Solution {
public IList<string> FullJustify(string[] words, int maxWidth) {
int n = words.Length;
int[] dp = new int[n + 1];
int[] path = new int[n];
Array.Fill(dp, int.MaxValue);
dp[n] = 0;
for (int i = n - 1; i >= 0; i--) {
int lineLength = -1;
for (int j = i; j < n && lineLength <= maxWidth; j++) {
lineLength += words[j].Length + 1;
if (lineLength - 1 <= maxWidth) {
int lastCost = j == n - 1 ? 0 : maxWidth - (lineLength - 1);
if (dp[i] > dp[j + 1] + lastCost) {
dp[i] = dp[j + 1] + lastCost;
path[i] = j + 1;
}
}
}
}
List<string> result = new List<string>();
int k = 0;
while (k < words.Length) {
int end = path[k];
StringBuilder line = new StringBuilder(words[k]);
for (int i = k + 1; i < end; i++) {
line.Append(' ').Append(words[i]);
}
line.Append(new string(' ', maxWidth - line.Length));
result.Add(line.ToString());
k = end;
}
return result;
}
}This C# implementation also utilizes dynamic programming to find the least-cost configuration of lines based on word inclusion. The resulting justified lines respect the discovered optimal path ensuring the efficient use of space on each line.