I am trying out Leetcode problem 68 and I need your help to asses the code. I am pretty new to this.
Given an array of strings
words
and a widthmaxWidth
, format the text such that each line has exactlymaxWidth
characters and is fully (left and right) justified.You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces
' '
when necessary so that each line has exactlymaxWidth
characters.Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.
For the last line of text, it should be left-justified and no extra space is inserted between words.
Note:
A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed
maxWidth
. The input arraywords
contains at least one word.
Example 1:
Input: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
Output:
[
"This is an",
"example of text",
"justification. "
]
Example 2:
Input: words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
Output:
[
"What must be",
"acknowledgment ",
"shall be "
]
Explanation: Note that the last line is "shall be " instead of "shall be", because the last line must be left-justified instead of fully-justified. Note that the second line is also left-justified because it contains only one word.
Example 3:
Input: words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"], maxWidth = 20
Output:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
Constraints:
1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100
words[i].length <= maxWidth
I want to know if I can optimize this solution.
Full Disclaimer: My friend helped me out with this solution.
Approach : Dynamic Programming
Time Complexity : O(n)
Space Complexity : O(n)
My solution is as follows:
class TextJustification(object):
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
# assign variables that you are going to use them later
idx = 0
ans = []
temp = []
temp_str = ''
temp_len = 0
# start the for-loop and end it when it reaches the last word.
while idx < len(words):
# take the word that we are currently looking at
word = words[idx]
"""
projected_len describes the length the line will have if the current word is added. If temp list is empty, then there wont be any extra space. As in if there is only one word in the line, the extra spaces can be added after words. If there are more than 1 word in a line, we need to get an extra space that will come before the 2nd word so there is a space between 1st word and 2nd word.
"""
if len(temp) == 0:
projected_len = len(word) + temp_len
else:
projected_len = len(word) + temp_len + 1
if (projected_len) <= maxWidth:
"""
The same logic is here. If the len of temp is zero means that yet there is no word in a possible line so no need to add 1 to that space. If the len is non-zero, we need to add 1 space that will be added after the 1st word and before 2nd word.
"""
if len(temp) != 0:
temp_len += 1
idx += 1
temp.append(word)
temp_len += len(word)
"""
If the program comes here to run, we know that there is only going to be one word in the line and hence we just add extra spaces at the end and append to the ans array.
"""
elif len(temp) == 1:
temp_str = temp[0] + ' ' * (maxWidth - len(temp[0]))
temp.clear()
ans.append(temp_str)
temp_str = ''
temp_len = 0
else:
"""
This tells us how many partitions will be made, which will be less than the length of the array.
"""
partitions = len(temp) - 1
# this tells us what is the combined length of all the words that are in temp array
total_words_len = temp_len - len(temp) + 1
# this gives us the total spaces that we need to divide among the words that we have
spaces_to_divide = maxWidth - total_words_len
# if partitions:
# this tell us the spaces that wont be equally divided
remainder_spaces = spaces_to_divide % partitions
# this tells us the spaces that will be equally divided
space_with_each_partition = spaces_to_divide // partitions
for temp_idx in range(len(temp)):
# For every partition, there will be spaces at the end of that word. This can't happen at the end of the word, hence this if condition and we decrement the partitions variable to detect that
if partitions:
temp_str += temp[temp_idx] + ' ' * space_with_each_partition
partitions -= 1
else:
temp_str += temp[temp_idx]
"""
We are told in the question that " If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right." So we keep adding an extra space every time we get to know that there is a remainder space.
"""
if remainder_spaces:
remainder_spaces -= 1
temp_str += ' '
# Now we are out of the loop that adds spaces. So, we clear all the variables and append the string to the array
temp.clear()
ans.append(temp_str)
temp_str = ''
temp_len = 0
"Here we do this to check if there is any word in the temp array, If so we execute the following condition."
if temp:
temp_str = ''
# This is to gather all the words in the array to a string
for temp_idx in range(len(temp)):
temp_str += temp[temp_idx]
temp_str += ' '
# As I mentioned before that there is no need for space at the end of the word so we remove the space that we added at the end of the last word:
temp_str = temp_str[:-1]
# add the spaces that are needed at the end of the array
new_temp_str = temp_str + ' ' * (maxWidth - len(temp_str))
# append last line to the final array
ans.append(new_temp_str)
# return the ans
return ans