Word Wrap

• Let' suppose we're at the ith word and jth line
• Suppose we can put 5 words(total characters which are less than m) in the jth line(wi,wi+1......wi+4).
• Now in this jth line, we will check all the different possibilities, for example, 1 word in the jth line, 2 words in a jth line and so on.
• In each possibility, we will add the cost corresponding to the extra spaces in the jth line, i.e the number of total extra spaces we have to add to make a total of m characters.
• Now we will take the optimal answer from the different possibilities we have i.e inserting only 1 word, 2 words...and so on in this jth line.

• Let' suppose we're at the ith word and jth line
• Suppose we can put 5 words(total characters which are less than m) in jth line(wi,wi+1......wi+4).
• Now in this jth line, we will check all the different possibilities, for example, 1 word in the jth line, 2 words in a jth line and so on.
• In each possibility, we will add the cost corresponding to the extra spaces in the jth line, i.e the number of total extra spaces we have to add to make a total of m characters.
• Now we will take the optimal answer from the different possibilities we have i.e inserting only 1 word, 2 words,..and so on in this jth line.
• Now as it is clear from the above steps that we are calling the function recursively at each step, so the time complexity will now be exponential. Hence to reduce the time complexity, we will use the technique of memoization(Dynamic Programming).
• From Observation, it can be clearly seen that there are overlapping subproblems.
• Hence, we will make a 2-Dimensional array of size N^2 to maintain the states of the dp, here the statedp[i][j] represents the minimum cost of the ith word at the start of the jth line.
  • We will be trying out all the possibilities and we know that with N-words, there can be at most N lines(only 1 word in each line). wordsLength is a vector of size N, containing lengths of N-words and maxLimit is the number of characters we want in each line.
  • For calculating the minimum cost, we will make calculateCost() in which we will pass the following arguments -
    • Current word at which we are
    • Current line at which we are
    • Vector of lengths of words
    • The character required in each line
  • We will check for different possibilities we can have at different values of i and j and make the optimal choice out of it.
  • For example, if we can insert 4 words in line j starting from ith word i.e.(i,i+1,i+2,i+3) and we will check 4 different possibilities we can have in this line starting with the word i.
    • insert only one word in line j i.e.(ith word) and move to the next line.
    • insert only two words in line j i.e.(ith and (i+1)th word) and move to the next line.
    • insert only three words in line j i.e.(ith,(i+1)th and (i+2)th word) and move to the next line.
    • insert only four words in line j i.e.(ith,(i+1)th, (i+2)th and (i+3)th word) and move to the next line.
  • The possibility that will give me the minimum cost, I will go for that.
  • To make the solution run faster, we will use the technique of memoization i.e. we will not calculate the answers for the states we have already calculated earlier.
  • For this, we will maintain a 2-D vector that will store the minimum cost for all combinations of i and j i.e. dp[i][j] = minimum cost to insert words starting from ith word and starting in the jth line.
  • Now, along with the 4 arguments in the calculateCost() function, we will be passing also the DP vector so finally there will be 5 arguments for the optimised solution.
  • Our answer will be equal to dp[0][0], i.e starting from the first word and the first line.

In This Approach, we will calculate the cost of all possible lines using dynamic programming and then calculate the final cost by taking the minimum from every possible line.

The steps are as follows:

• Take a vector “len” in which we will store the length of every given string.
• Take a 2D array “cost” to store the cost of every possible line which can be formed using the given lengths.
• Now iterate through the array “len” from 0 to n-1(say iterator be i):
  • If we are taking only one element in the current line then the cost[i][i] will be “m” - “len[i]”.
  • Now iterate through the array from i+1 to n-1(say iterator be j):
    • Update the value of “cost[i][j]” such that ‘i’ denote the line number and j denote the number of elements in the current line.
    • “Cost[i][j]” will be cost[i][j - 1] - len[j] - 1.
• Now iterate through the cost array again to update all the values which are less than 0 to be INT_MAX.
• Else update the cost[i][j] to cost[i][j] ^ 3.
• Take an array “mincost” of length n in which we will store the minimum cost of taking every element from the list.
• Iterate through the array from n-1 to 0(say iterator to be i):
  • Update mincost[i] = cost[i][n - 1] denoting that the minimum cost of making word wrap from current element to the final element is cost[i][n - 1].
  • Now iterate through the array from n-1 to ‘i’(say iterator be j):
    • Check if the value of “mincost[i]” can be minimized using by changing the line at index ‘j’. If it can be minimised then update the value of “mincost[i]” = “cost[i][j - 1]” + “mincost[j]”.
• Finally, return “mincost[0]”.