Word Wrap Problem | DP | A Dynamic programming solution for Word Wrap Problem in Javascript ; 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 ) ; For simplicity , 1 extra space is used in all below arrays 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
let MAX = Number . MAX_VALUE ; function printSolution ( p , n ) { let k ; if ( p [ n ] == 1 ) k = 1 ; else k = printSolution ( p , p [ n ] - 1 ) + 1 ; document . write ( " " + " " + k + " " + " " + " " + p [ n ] + " " + " " + " " + n + " " ) ; return k ; } function solveWordWrap ( l , n , M ) { let extras = new Array ( n + 1 ) ; let lc = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { extras [ i ] = new Array ( n + 1 ) ; lc [ i ] = new Array ( n + 1 ) ; for ( let j = 0 ; j < n + 1 ; j ++ ) { extras [ i ] [ j ] = 0 ; lc [ i ] [ j ] = 0 ; } } let c = new Array ( n + 1 ) ; let p = new Array ( n + 1 ) ; for ( let i = 1 ; i <= n ; i ++ ) { extras [ i ] [ i ] = M - l [ i - 1 ] ; for ( let j = i + 1 ; j <= n ; j ++ ) extras [ i ] [ j ] = extras [ i ] [ j - 1 ] - l [ j - 1 ] - 1 ; } for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = i ; j <= n ; j ++ ) { if ( extras [ i ] [ j ] < 0 ) lc [ i ] [ j ] = MAX ; else if ( j == n && extras [ i ] [ j ] >= 0 ) lc [ i ] [ j ] = 0 ; else lc [ i ] [ j ] = extras [ i ] [ j ] * extras [ i ] [ j ] ; } } c [ 0 ] = 0 ; for ( let j = 1 ; j <= n ; j ++ ) { c [ j ] = MAX ; for ( let i = 1 ; i <= j ; i ++ ) { if ( c [ i - 1 ] != MAX && lc [ i ] [ j ] != MAX && ( c [ i - 1 ] + lc [ i ] [ j ] < c [ j ] ) ) { c [ j ] = c [ i - 1 ] + lc [ i ] [ j ] ; p [ j ] = i ; } } } printSolution ( p , n ) ; } let l = [ 3 , 2 , 2 , 5 ] ; let n = l . length ; let M = 6 ; solveWordWrap ( l , n , M ) ;