# Minimum Raggedness Line Wrap

• Given a list of strings, wrap them in a way to minimize the sum of squared space left over in each line.

• @bigoffer4all Classical dynamic programming problem

``````def textJustification(words,m):
bad = [[i - j + sum(len(s) for s in words[j:i + 1]) for j in range(len(words))] for i in range(len(words))]
dp = list(range(len(words) + 1))
for i in range(1, len(dp)):
res = float('inf')
for j in range(1, i + 1):
diff = m - bad[i - 1][j - 1];
if (diff >= 0):
res = min(diff * diff + dp[j - 1], res)
dp[i] = res
return dp[len(words)]``````

• @elmirap can you explain your code?

• @agave I will make a try to explain the algorithm

1. try to arrange each sequence of words [i..j] (i <=j) in a line and calculate number of left spaces in the line
m - (j-i)-(len_i+...len_j), where m - line length, len_i - length of word i
In case sequnce f words [i..j] can't fit in a line, we set the number of spaces to Infinite value.
example words ["leet","code"]
we compute for word sequences [leet] ,[leet,code],[code]. Lets store these costs in some array
This information is kept in variable diff.
2. We appply the following recursive formule :
DP[i] = min(DP[j]+diffdiff) for j <i, which mean the following
To arrange the first i words in an optimal way (with minimum number of spaces) you need to find such word j < i so that you can break the sequence at word j and words[j+1,i] will be written in a new line. You assume all words up to j has already been arranged in optimal way, so you know DP[j] and need to select j in such way that DP[j]+diff
diff should be minimal
If something is not clear let me know

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.