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
- 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.
- 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]+diffdiff 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.