TEXT JUSTIFICATION - LEETCODE # 68 | GOOGLE INTERVIEW QUESTION | PYTHON
Vložit
- čas přidán 14. 03. 2022
- In this video we are solving a popular Google interview question: Text Justification (Leetcode 68). This problem was not fun to solve so make sure you subscribe because I was pulling my hair out trying to find out an easy solution for you guys!
The solution is really intuitive on paper but when you try to code it you'll notice there are annoying edge cases to take care of so let's work through it together and hopefully it makes sense by the end of the video. - Věda a technologie
For anyone who had trouble understanding spaces = maxWidth - width + len(cur_line)
maxWidth represents the max width we have available for the line.
width is the space we have already used.
At this point, we have already allocated a single space per word in the above if condition. At this point in the problem, we already know that each word can fit into the line with AT LEAST one single space separating them. To make this part of the problem easier, we can just add those single spaces back to the remaining space we are allowed to distribute which would be represented by the length of cur_line (each word would be one single space).
So
spaces (available spaces left to distribute) = maxWidth - width (what we have already used) + len(cur_line) (add back in the single space per word we have already used in the prev if condition).
Dude bless man. I was so confused why he addded back the Len of the array. This helped a lot. Thank you
I was lost here and came to see comments.. Thanks for the rescue :)
this makes sense thank you. I was confused why we would add back len(cur_line) and not take 1 off that, but I remember we always add space per word in width, even if it's the last word in the line, so we need to remove that many words. Really all we're doing is taking max width and subtracting the amount of actual chars, but
width = number of chars in words + space per word
so number of chars in words + space per word - 1 per word = number chars in words in that line
Very good solution! Have my onsite with Google in a week and this channel is a gold mine!! Definitely subscribed.
Thanks for the kind words and best of luck with your on-site! I hope you smash it and get that offer
came for the solution, stayed and subbed for an awesome non DP sol and also not get karma 😂😂
thanks for keeping it fun!
Great Explanation but a little confusing for spaces. Keep up the work!
ok man quit berating. I subscribed.
loved the intro!subscribed!
Haha anything to get those likes up
what is the purpose of adding len(cur_line) in the else case? can't we get the leftover space bu subtracting the maxWidth from the space already comsumed?
Condition 1: we can add word to current line.
- when you are adding a word to the current line, we need to also consider the fact that each word is separated by a space. Therefore, we would need to include +1 to the current line width for each word added. However, we did not actually modify the word to the string at this point. We will continue this process until the next word would have exceeded the maximum length.
Condition 2 - we can’t add the current word to the current line
- At this step, we will need to calculate the number of spaces to distribute between each words excluding the last one in the current line. To calculate the available spaces
`spaces = maxWidth - width + len(cur_line)`
- we have to add back the len(cur_line) because we included the string count when we were comparing and adding the words in condition one. However, none of the words were modified and we need to add these values back in order to calculate the number of spaces available to us.
Hope this helps.
I am having trouble understanding why we defining j>=len(cur_line) -1
We ar iterating j from 0 till cur_lin , so y can't we definite j == len(curline) -1 instead
I tried using == but it is throwing out of index error, but how come j is Incrementing > len(curline)-1
When it matches to len(curline) -1 it should auto set j to 0 right?
why are we not considering time complexity of 2nd while loop for spaces
"But the actual solution is a pain in the ass" LOL
yeah it is, I've solved this problem before and there are a lot of things to take care of...
Yea I typically hate any question that's HARD level and Google tagged because you already know it's gonna be some bullshit lmao
@@crackfaang 😂😂😂
L14 - we increment the width by the length of the word plus space each time. Don't we want to skip the space for the last word? How was that handled?
I am surprise the code work without handling that edge case.
While I use "for i in range(len(words)): ", instead of i < len(words). What is the reason of it for showing index out of bounds in the line of "curr_line[-1] += " " * (maxWidth - width + 1)"?
You've probably already figured it out by now, but it's because the for-loop increments i each time. So it's not looping through and adding each word correctly.
The reason we use a while-loop is because we don't want to increment our index i when we're going through the else: statement
hahaha subscribed !! xD
Now i hope to get selected for google !!
i was so so so close to subscribing but then you went and TOLD me to, tf man
lol "if you don't subscribe bad karma, you are going to fail. "
Haha a little bit of fun there… a lot of people free loading these videos man! If everyone subscribed I’d have a lot more subscribers 😂😂😂
@@crackfaang they will deserve it. At least a hit in the like button.
I am unable to understand the else block :((((
isn't it suppose to be DP problem ? how come simple solution is possible ?
Most questions can be solved in different ways. I don't do Dynamic Programming on this channel because it's just a garbage way of solving questions and literally never used in real life. If there exists a non-DP solution, I will always show that here.
@@crackfaang i subscribed just because of this comment
lol bad karma.. dude is funny!
Haha gotta get those likes up ya know!