Minimum Raggedness Line Wrap


  • 0
    B

    Please refer https://en.wikipedia.org/wiki/Line_wrap_and_word_wrap#Minimum_raggedness.

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


  • 0

    @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)]

  • 0

    @elmirap can you explain your code?


  • 0

    @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

Log in to reply
 

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