The Text Justification problem is a classic example of a dynamic programming problem. Given a sequence of words and a line width, we want to minimize the "badness" of the text justification. The badness is defined as the sum of the cubes of the number of spaces needed to pad out a line, so we want to minimize the sum of the cubes of the number of spaces needed to justify all the lines.
The dynamic programming solution to Text Justification can be solved in two steps:
Step 1: Compute the cost of every possible line break.
The first step is to compute the cost of every possible line break. This can be done using a dynamic programming table where the cost of a line from i to j is stored in the table. We start with the last word in the sequence and work our way backwards, computing the cost of each possible line break from i to j. The cost of a line is defined as (line_width − total_words_width)3, where total_words_width is the sum of the widths of the words in the line.
We can compute the cost of every possible line break using a nested loop:
int[][] cost = new int[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
int total_width = get_total_width(i, j);
if (total_width > line_width) {
cost[i][j] = Integer.MAX_VALUE;
} else if (j == n-1) {
cost[i][j] = (int) Math.pow(line_width - total_width, 3);
} else {
for (int k = j+1; k < n; k++) {
int new_cost = cost[j+1][k] + (int) Math.pow(line_width - total_width, 3);
if (new_cost < cost[i][j]) {
cost[i][j] = new_cost;
}
}
}
}
}In this code, we start with the last word in the sequence (i.e., j = n-1) and work our way backwards. If the total width of the words from i to j exceeds the line width, we set the cost to infinity since this line cannot be justified. Otherwise, we compute the cost of the line as described above. If j is the last word in the sequence, there is only one line so the cost is simply the badness of that line. If j is not the last word in the sequence, we try every possible line break after j and choose the one with the minimum cost.
Step 2: Compute the optimal solution.
The second step is to compute the optimal solution using the table of costs that we computed in Step 1. We start at the beginning of the sequence and work our way through, computing the optimal line breaks using the previously computed costs.
int[] linebreaks = new int[n];
int[] optimal_costs = new int[n];
for (int i = n-1; i >= 0; i--) {
int min_cost = Integer.MAX_VALUE;
int min_k = n-1;
for (int j = i; j < n; j++) {
int cost = cost[i][j];
if (cost != Integer.MAX_VALUE) {
int total_cost = cost + (j == n-1 ? 0 : optimal_costs[j+1]);
if (total_cost < min_cost) {
min_cost = total_cost;
min_k = j;
}
}
}
optimal_costs[i] = min_cost;
linebreaks[i] = min_k;
}In this code, we start at the beginning of the sequence and work our way through, computing the optimal line breaks using the previously computed costs. For each i, we try every possible line break to find the one with the minimum cost. If there is no valid line break from i (i.e., the cost is infinity), we set the optimal cost to infinity as well. Otherwise, we compute the total cost (i.e., the current line’s cost plus the optimal cost from the next line) and check if it is smaller than the current minimum cost. If it is, we update the minimum cost and the corresponding line break index.
After the final iteration, the array of line breaks contains the optimal line breaks for the text justification.
Here is the complete code:
public static List<String> justify(String[] words, int line_width) {
int n = words.length;
// Step 1: Compute the cost of every possible line break.
int[][] cost = new int[n][n];
for (int i = n-1; i >= 0; i--) {
for (int j = i; j < n; j++) {
int total_width = get_total_width(words, i, j);
if (total_width > line_width) {
cost[i][j] = Integer.MAX_VALUE;
} else if (j == n-1) {
cost[i][j] = (int) Math.pow(line_width - total_width, 3);
} else {
for (int k = j+1; k < n; k++) {
int new_cost = cost[j+1][k] + (int) Math.pow(line_width - total_width, 3);
if (new_cost < cost[i][j]) {
cost[i][j] = new_cost;
}
}
}
}
}
// Step 2: Compute the optimal solution.
int[] linebreaks = new int[n];
int[] optimal_costs = new int[n];
for (int i = n-1; i >= 0; i--) {
int min_cost = Integer.MAX_VALUE;
int min_k = n-1;
for (int j = i; j < n; j++) {
int cost_ij = cost[i][j];
if (cost_ij != Integer.MAX_VALUE) {
int total_cost = cost_ij + (j == n-1 ? 0 : optimal_costs[j+1]);
if (total_cost < min_cost) {
min_cost = total_cost;
min_k = j;
}
}
}
optimal_costs[i] = min_cost;
linebreaks[i] = min_k;
}
// Construct the lines.
List<String> lines = new ArrayList<>();
int i = 0;
while (i < n) {
int j = linebreaks[i];
int width = get_total_width(words, i, j);
StringBuilder line = new StringBuilder();
line.append(words[i]);
for (int k = i+1; k <= j; k++) {
line.append(' ');
line.append(words[k]);
}
for (int k = 0; k < line_width - width; k++) {
line.append(' ');
}
lines.add(line.toString());
i = j+1;
}
return lines;
}
private static int get_total_width(String[] words, int i, int j) {
int width = j - i; // Space width.
for (int k = i; k <= j; k++) {
width += words[k].length();
}
return width;
}To use the above code, simply call ‘justify(words, line_width)‘ where ‘words‘ is an array of strings representing the words in the text and ‘line_width‘ is the desired line width. The function returns a list of strings representing the lines of justified text.