LeetCode 68. Text Justification

Question

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 width maxWidth, format the text such that each line has exactly maxWidth 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 exactly maxWidth 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 array words 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

Answer 1

Don't use pointless classes. TextJustification isn't doing anything, and self is never used. Just write an ordinary function.

The comment formatting is unusual and awkward. (1) Doc-string are intended to document a class, function, or method. They are not intended as a fancy device for ordinary code comments. (2) Do your reader a favor and line-wrap those extra long comments.

Needless verbosity can undermine the effectiveness of code comments. It's excellent that you are striving to write readable, well-documented code. However, comments work best when they reinforce code clarity rather than trying to carry the burden on their own. And if the comments become too verbose, most readers will abandon them and simply read the code (that's what I did, for example, when experimenting with your program). Always place most of your emphasis on writing clear code with well-named functions and variables (more below). Once that foundation is in place, use comments judiciously to provide additional context and organizational cues to the reader. In many cases, such comments can be quite brief (again, see below). Finally, one almost never needs comments that merely state what is already obvious from the code. Here's one of several examples of that kind of thing from your code:

# 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]

When feasible, use substantive names rather than generic or abstract names. Your primary status-tracking variables are idx, ans, temp, temp_str, and temp_len. The first name is fine, although I would tend to shorten to just i, which is a thoroughly conventional and well-understood name for a sequence index. The other names, however, are more abstract than substantive. What is temp? It's a sequence of words for the current line, so names like words or current or even curr would be better. What is temp_str? It's a line of text, so line or text would be better. And what is ans? It is a sequence of lines, so call it that.

The current program gets stuck if max width is too low. You should either raise an exception or shove at least one word on every line.

A Python bool can function as an integer. In a couple cases, your logic can be simplified by taking advantage of the fact that True and False can also be used numerically as 1 and 0.

The three-part if-else structure forces you to repeat variable resetting code. Most of the code resides in a three-part conditional structure: one branch if the word fits in the current line; and two branches when it doesn't, one for a single-word line and one for multi-word line. That logical structure forces you to repeat the variable-resetting code in the latter two branches. In such situations you should rearrange things either by handling the first branch separately and then using continue, or by using two layers of if-else branching. Alternatively (and this is the route I ended up pursuing below), you can try to generalize the logic a bit, eliminating the need to worry about the distinction between single-word and multi-word lines.

Keep your main algorithm simpler by delegating secondary calculations to utility functions. Your code handles two main tasks: grouping words that will fit into a line; and building a padded line from those words. Moving the line-padding logic to a separate function is especially helpful in your case, because you have three somewhat-repetitive chunks of padding code to handle a single-word line, a multi-word line, and the non-justified final line. Moving padding to a function eliminates most of that repetition and consolidates the logic in one spot, which improves readability.

Some alternative padding logic to consider. Your primary logic for line padding is reasonable, but it is overburdened by comments is more complex that it needs to be. Here's how I approached the problem. Every line consists of a sequence of pairs: each word is followed by zero or more spaces. So the primary task is to compute the padding widths, both for the justify case and for the final-line case. I started by knowing the the basic structure of the function I wanted:

def padded_line(words, max_width, justify):
    if justify:
        widths = ...
    else:
        widths = ...
    return ''.join(
        w + (' ' * wid)
        for w, wid in zip(words, widths)
    )

In the justify = True case, we need to figure out the total number of spaces to be added to the line and then allocate that space among the gaps between the words. When that allocation cannot be perfectly even, we want the remainder to be distributed among the initial words in the line. And the final width is necessarily zero, because we are fully justifying the line. In the justify = False case, the widths between the words are all one, and the rest of the space is given to the last width. Here's what I ended up with. Among other things, note the commenting strategy: most of the clarity comes from variable naming and algorithmic simplicity; the comments are brief and mostly play an organizational role in this case. Finally, note the use of a bool in an arithmetic context to distribute the remainder.

def padded_line(words, max_width, justify):
    # N of spaces to be distributed among the gaps.
    n_spaces = max_width - sum(len(w) for w in words)
    n_gaps = len(words) - 1

    # Compute padding widths.
    if justify:
        wid, remainder = divmod(n_spaces, n_gaps)
        widths = [wid + int(i < remainder) for i in range(n_gaps)]
        widths.append(0)
    else:
        widths = [1 for _ in range(n_gaps)]
        widths.append(n_spaces - n_gaps)

    # Return padded line.
    return ''.join(
        w + (' ' * wid)
        for w, wid in zip(words, widths)
    )

Justifying the text: code clarity enhanced by judicious commenting. With that utility function in place and with the other suggestions discussed above, we end up with the following code to justify the text. Again, note the comments: even though they are quite brief, they help with readability by giving context (eg, explaining how we are using the 3 primary variables), by providing reasoning and narrative (eg, the comments in the three if-else branches), or merely by providing simple organizational cues (eg, "Process the words" and the last comment, neither of which is very substantive, maintain organizational symmetry across the code by ensuring that every code sub-section starts with a comment). Even though the comments do aid readability in notable ways, most of the clarity comes from the code itself: substantive naming, intuitive algorithmic strategy and structure, and delegating computational details to other functions.

def full_justify(words, max_width):
    # All lines, the words for current line, and their combined width.
    lines = []
    curr = []
    width = 0

    # Process the words.
    N = len(words)
    i = 0
    while i < N:
        word = words[i]
        new_width = width + len(word) + bool(curr)
        if new_width <= max_width:
            # The word fits: add it to current line.
            i += 1
            curr.append(word)
            width = new_width
        elif curr:
            # The word does not fit: build the current line and reset.
            lines.append(padded_line(curr, max_width, justify = True))
            curr = []
            width = 0
        else:
            # The word does not fit, even by itself.
            raise ValueError('max_width cannot be less than the smallest word width')

    # Handle words for last line and return.
    if curr:
        lines.append(padded_line(curr, max_width, justify = False))
    return lines