Text Justification Dynamic Programming

hello friends my name is Tushar and today I'm going to discuss the question text justification so the question is given a list of words and a limit or number of characters you can print on every line how do you arrange this words or multiple lines such that the number of empty spaces is evenly distributed so here I have five strings - char Roy likes to code and the width of my screen is 10 so I can have only ten characters on my every line so how do I arrange this words or multiple lines such that the number of empty spaces is evenly distributed first let's look at a greedy way of doing this so the greedy ways is that put as many words as possible on each line and if the next word cannot fit in this line go to the next line and continue the process so so the greedy arrangement for this strings for this list of strings will be too short space and then draw so this is total of 10 characters so we go to the next line likes - this is total of eight characters so we go to the next line code let's look at another alternate arrangement - char row I likes to code so we have two arrangements and so now that now the question is which of this arrangement distributes the empty spaces evenly over multiple lines so let's see how many empty spaces we have on each line so this is total of 10 characters this empty space does not count because this is used to separate two words so this has zero empty space because the total length here is 10 this has two empty space because the total length from here to here is eight five six seven eight and this has six empty spaces because force four characters and then turn empty spaces let's look at this arrangement this is six so this has four empty spaces this is three four five six seven eight nine so this is one empty space and this is two three four five six seven so this is three empty space so if you just add up the empty spaces on each of this so this is nine and this is this is eight and this is also eight so this doesn't help because the sum of empty spaces or multiple lines for both the Arrangements is same so let's do another thing let's try to do the square of sum of the square of the empty spaces so then our thing is zero squared plus two squared plus six square and this is four squared plus one squared plus three squared so this is four plus 36 so this is 40 and this is 16 plus one plus nine so this is 26 so here this arrangement is bad it better than this arrangement because this number is less than this number so we are basically going to use the square of the empty spaces on each line sum of square of empty spaces on each line to measure the badness of the arrangement as you can see more than empty spaces on each line higher the number and square of this number is going to be way worse than the just this number by itself so how we are going to solve this yes we're going to use Daniel programming to solve this question so here I have a 5 cross 5 matrix because I have total of 5 strings let's see how I'm going to fill this matrix so this is a Cosme tricks let's see how this works so if I am filling here 0 to 0 so what is the cost of storing strings starting from 0 and ending at 0 in one line so if I stored to shore in one line the total number of empty spaces would be 4 so here I'm going to store for a square of 4 so that's 16 let's go here 0 2 1 if I were storing 0 & 1 in one line total number of empty spaces would be 0 because this has 6 space this takes 6 spaces then there is a space between them then this takes three spaces the pool of ten spaces so the number of empty spaces would be 0 so this is 0 to 1 is 0 because 0 squared is 0 0 to 2 0 1 & 2 you cannot fit all this in one line so this value will be infinity 0 to 3 you cannot fit from 0 to 3 in one line so this value is also infinity and 0 to 4 you cannot fit all this words in one lines of this value is also infinite so let's fill one cross 1 so 1 Cross 1 what is the cost of storing this in one line so my width is 10 this is 3 characters so I am left with 7 characters so this will store 7 squared which is 49 1 comma 2 so likes is 5 characters Roy is three characters likes is 5 characters so 3 plus 5 8 and then one space between them so that's 9 so I am left with one empty character 1 empty space so 1 square is 1 1 2 3 1 2 3 cannot fit in one line because three plus five is eight plus two 10 and then two spaces between them is 12 so this is infinite and 1 2 4 also cannot fit in one lines of this is also infinite let's look at 2 2 2 2 so if we just store likes and one line I will be left with five empty spaces because likes is of length 5 so 5 squared is 25 to 2/3 if I had lights and two on one line so that is 5 + 2 7 + 1 and he stays within an 8 so I am left with 2 empty spaces so 10 minus 2 is 4 10 minus 2 is 2 and 2 squared is 4 and 2 2 4 so this is more than 10 characters so this is infinite let's look at 3 2 3 three-two-three if you stored in one line will be left with eight empty spaces so this is 64 and three to four if both of them were in one line so 2 + 1 squares between them 3 + 4 7 so so this is 3 squared which is 9 and finally 4 - 4 so this is this is 4 so 10 minus 4 is 6 so this is 36 in my code to get this I have two different sets of for loop so that I can get it done in off and square time but here the way I calculated it I just did it in one forty one traversal of this matrix so next let's look at how I'm going to use this information to decide from which line we go to at which point we're able to put the line breakers so here I have two additional arrays of the same length as the number of strings this is going to show the minimum cost well this is going to store the final result let's start I and J from the end we could also start I and J from the left and go right but we here we're going to start ing from the right and go left so when I and J is for we just have one string for and the cost of storing this string is 4 comma 4 so that's 36 and here I'm going to put a value file saying that starting from 4 till 5 but not including 5 will begin on one line then I decrement my I by 1 and J stays at end so first I check is just 3 to 4 exists can stay in one line so we go to 3 to 4 and that's 9 so we can have 3 to 4 in one line so we put a value 9 here and we put a value 5 here so again say 3 to 5 will be on one line excluding 5 so then we decrement I by 1 and G again stays at the end so first thing which I guess can't do the for existing one 9 so 2 to 4 is infinity so they cannot exist in one line so there you have to check at what point we split it so let's try to split it for so when J is equal to 4 what I'm saying is I'll have something like likes two on one line and code on another line so the cost of likes to two to three is four so the cost of splitting at college four is four plus the best we can do from Jay till the end and that's 36 so the total cost is 40 so if we split from Jay Z before the total cost is 40 let's try to split from J is equal to three so when J is equal to three I'm saying lights will be on one line and two code will be on another line likes to code when we do this arrangement the cost is 2 to 2 so 2 to 2 is 25 plus the cost from J to the end so that's 9 so this is 34 so this value is less than for the web so for J is equal to 3 is better than J is equal to 4 so here we will use this at 34 and we'll put 3 here so basically from starting from 2 till 3 excluding 3 will be one line then we go to 3 starting from 3 till file excluding 5 will be on another line let's decrement I by 1 and J again goes to the end 0 to 1 to 4 cannot be on one line so let's try splitting J is equal to 4 if we try spreading J 4 1 2 3 can 1 2 3 be on 1 line 1 2 3 is also infinity so we cannot split from we cannot have Roy likes to on one line and code another line so let's split from J is equal to 3 when we try to split J is equal to 3 what I'm saying is checking the cost of 1 to 2 cost of having 1 to 2 on one line so 1 to 2 is 1 plus 3 to 4 so that's 9 yeah best we can do till J 2 then so that's 9 so this is 10 so when J is equal to 3 the value is 10 and let's try J is equal to 2 so for J is equal to cost of 1 1 cost of 1 is 49 plus the best I can do from J to Len and that's 34 so this number is going to be greater than this number so we'll put 3 here we'll put the minimum cost here so that's 10 and we'll put 3 here all right let's try I is equal to 0 J again goes at the end 0 to 4 cannot fit in one line so J decrements by 1 0 2 0 to 0 to 14 are denser 0 2 sorry J stays here 0 to 3 cannot fit in one line so J decrements by 1 0 to 2 cannot fit in one line so J again decrement by one we are looking for the place to split so 0 to 1 so 0 to 1 is 0 so when J is equal to 2 the cost is 0 plus the best we can do till this point is 34 let's try J is equal to 1 when J is equal to 1 the cost is 0 0 so that's 16 plus the best we can do till 1 from one to the other that's 10 so this is 34 and this is 26 so J is equal to 1 is better so this value is 20 the cost is 26 and we say 1 so this is it the minimum cost to arrange this is 26 and this is we are going to use this array to get the final result so let's start from here so what I'm saying is 0 till 1 but excluding 1 will be on one line so 0 is too short so Tushar is on one line then you go to 1 because this value is 1 so 1 2 3 excluding 3 will be on one line so row I likes then we go to three so three will end will be under one line so to code again let's calculate the cost here so the number of empty spaces here is for the more of empty space here is to one because this is three four five six seven eight nine and number of empty space here is two three four five six seven three square of them will be 16 one and nine and this value is twenty six and our minimum cost was also twenty six so this arrangement will be the best arrangement we can do such that the empty spaces are evenly dissipated among multiple lines let's analyze the run time complexity space complexity is pretty clear over n square time complexity is to build this matrix if you look at the code I have split it into multiple for loops and to build this matrix it will take off n square time and then here we move through I and J and then also to boil over n squares time so the time complexity for this algorithm will also be off and square finally let's look at the formula for this one assuming that I have built my cost matrix C two-dimensional cost matrix my minimum cost will be M of I is equal to minimum of M of J plus C of I 2 J minus 1 where J goes from I plus 1 to the length of the array the full solution for this problem is in the description section of this video you can also check out my github link github.com mission peace interview wiki and you could subscribe my youtube channel youtube.com/ user to show right if identified finally I would like to request the viewers to improve my get repository by contributing to it all you have to do is send me a good pull request and I will review the change and if the change looks good I will pull it in into my git repository alright thanks for watching this video

Channel: Tushar Roy - Coding Made Simple

Views: 120,500

Rating: 4.5927978 out of 5

Keywords: text justification dynamic programming, text justification, word wrap dynamic programming, dynamic programming

Id: RORuwHiblPc

Length: 15min 31sec (931 seconds)

Published: Thu May 07 2015