DP #20. Text Justification - mbhushan/dynpro GitHub Wiki

(20). Text Justification.

Given a sequence of words, and a limit on the number of characters that can be 
put in one line (line width). Put line breaks in the given sequence such that 
the lines are printed neatly. Assume that the length of each word is smaller 
than the line width.

The extra spaces includes spaces put at the end of every line except the last one.  
The problem is to minimize the following total cost.
 Cost of a line = (Number of extra spaces in the line)^2
 Total Cost = Sum of costs for all lines

Text = "this is a cool problem to solve"
width = 10

Possible arrangement:
this is    3 (extra space)
a cool     4 (extra space)
problem    3 (extra space)
to solve   2 (extra space)

Total cost = (3^2) + (4^2) + (3^2) + (2^2)
           = 9 + 16 + 9 + 4
           = 38

Formula:

M[i] = M[j] + C[j+1][i]

C[][] is the cost matrix below.
M[] is the min cost array.
Indices keeps track of the split indices.

	this	is	a	cool	problem	to	solve
	0	1	2	3	4	5	6
0	36	9	1	inf	inf	inf	inf
1		64	36	1	inf	inf	inf
2			81	16	inf	inf	inf
3				36	inf	inf	inf
4					9	0	inf
5						64	4
6							25
Width	10
	0	1	2	3	4	5	6
Min Cost	36	9	1	25	34	25	38	<- final cost
Indices	0	0	2	2	4	4	5
0-1	this	is
2-3	a	cool
4-4	Problem
5-6	to	Solve

Text Justification

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)