Word Wrap Problem | DP | A utility function to print the solution l [ ] represents lengths of different words in input sequence . For example , l [ ] = { 3 , 2 , 2 , 5 } is for a sentence like " aaa ▁ bb ▁ cc ▁ ddddd " . n is size of l [ ] and M is line width ( maximum no . of characters that can fit in a line ) ; l [ ] represents lengths of different words in input sequence . For example , l [ ] = { 3 , 2 , 2 , 5 } is for a sentence like " aaa ▁ bb ▁ cc ▁ ddddd " . n is size of l [ ] and M is line width ( maximum no . of characters that can fit in a line ) ; extras [ i ] [ j ] will have number of extra spaces if words from i to j are put in a single line ; lc [ i ] [ j ] will have cost of a line which has words from i to j ; c [ i ] will have total cost of optimal arrangement of words from 1 to i ; p [ ] is used to print the solution . ; calculate extra spaces in a single line . The value extra [ i ] [ j ] indicates extra spaces if words from word number i to j are placed in a single line ; Calculate line cost corresponding to the above calculated extra spaces . The value lc [ i ] [ j ] indicates cost of putting words from word number i to j in a single line ; Calculate minimum cost and find minimum cost arrangement . The value c [ j ] indicates optimized cost to arrange words from word number 1 to j . ; Driver Code
INF = 2147483647 NEW_LINE def printSolution ( p , n ) : NEW_LINE INDENT k = 0 NEW_LINE if p [ n ] == 1 : NEW_LINE INDENT k = 1 NEW_LINE DEDENT else : NEW_LINE INDENT k = printSolution ( p , p [ n ] - 1 ) + 1 NEW_LINE DEDENT print ( ' Line ▁ number ▁ ' , k , ' : ▁ From ▁ word ▁ no . ▁ ' , p [ n ] , ' to ▁ ' , n ) NEW_LINE return k NEW_LINE DEDENT def solveWordWrap ( l , n , M ) : NEW_LINE INDENT extras = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE lc = [ [ 0 for i in range ( n + 1 ) ] for i in range ( n + 1 ) ] NEW_LINE c = [ 0 for i in range ( n + 1 ) ] NEW_LINE p = [ 0 for i in range ( n + 1 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT extras [ i ] [ i ] = M - l [ i - 1 ] NEW_LINE for j in range ( i + 1 , n + 1 ) : NEW_LINE INDENT extras [ i ] [ j ] = ( extras [ i ] [ j - 1 ] - l [ j - 1 ] - 1 ) NEW_LINE DEDENT DEDENT for i in range ( n + 1 ) : NEW_LINE INDENT for j in range ( i , n + 1 ) : NEW_LINE INDENT if extras [ i ] [ j ] < 0 : NEW_LINE INDENT lc [ i ] [ j ] = INF ; NEW_LINE DEDENT elif j == n and extras [ i ] [ j ] >= 0 : NEW_LINE INDENT lc [ i ] [ j ] = 0 NEW_LINE DEDENT else : NEW_LINE INDENT lc [ i ] [ j ] = ( extras [ i ] [ j ] * extras [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT c [ 0 ] = 0 NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT c [ j ] = INF NEW_LINE for i in range ( 1 , j + 1 ) : NEW_LINE INDENT if ( c [ i - 1 ] != INF and lc [ i ] [ j ] != INF and ( ( c [ i - 1 ] + lc [ i ] [ j ] ) < c [ j ] ) ) : NEW_LINE INDENT c [ j ] = c [ i - 1 ] + lc [ i ] [ j ] NEW_LINE p [ j ] = i NEW_LINE DEDENT DEDENT DEDENT printSolution ( p , n ) NEW_LINE DEDENT l = [ 3 , 2 , 2 , 5 ] NEW_LINE n = len ( l ) NEW_LINE M = 6 NEW_LINE solveWordWrap ( l , n , M ) NEW_LINE