Text justification

Question

This is the Text Justification challenge at LeetCode:

Given an array of words and a length \$L\$, format the text such that each line has exactly \$L\$ 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 \$L\$ characters.

Extra spaces between words should be distributed as evenly as possible. 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.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

["This    is    an",
 "example  of text",
 "justification.  "]

Clarifications:

1. For any two words, there is at least one space between them. This is also true for the last line.

2. A line other than the last line might contain only one word. In this case, the line should be left-justified.

class Solution:
    # @param {string[]} words
    # @param {integer} maxWidth
    # @return {string[]}
    def fullJustify(self, words, maxWidth):
        num_of_words = len(words)
        start_ind, end_ind, runner = 0, 0, 0
        len_of_line, word_num_line = 0, 0
        res = []

        while True:
            runner = start_ind
            if runner >= num_of_words:
                break
            len_of_line, word_num_line = 0, 0

            #find the start and end word indexes for one line
            while runner < num_of_words:
                len_of_line = len_of_line + len(words[runner])
                word_num_line = word_num_line + 1
                if runner != start_ind:
                    len_of_line = len_of_line + 1
                if len_of_line > maxWidth:
                    break
                runner = runner + 1

            #justify one line
            if runner != num_of_words:
                end_ind = runner - 1
                if start_ind == end_ind: #one word in a line
                    oneline = words[start_ind] + " "*(maxWidth-len(words[start_ind]))
                else: #many words in a line
                    len_of_line = len_of_line - len(words[runner]) - 1
                    word_num = end_ind - start_ind + 1
                    extra_spaces = maxWidth - (len_of_line - (word_num - 1))
                    basic_pad_spaces = extra_spaces // (word_num - 1)
                    addition_pad_spaces = extra_spaces % (word_num - 1)
                    oneline = ""
                    for ind in range(start_ind, runner-1):
                        oneline = oneline + words[ind] + " "*basic_pad_spaces
                        if ind - start_ind < addition_pad_spaces:
                            oneline = oneline + " "
                    oneline = oneline + words[runner-1]
            else: #last line
                oneline = ""
                for ind in range(start_ind, num_of_words-1):
                    oneline = oneline + words[ind] + " "
                oneline = oneline + words[num_of_words-1]
                pad_spaces = maxWidth - len(oneline)
                oneline = oneline + " "*pad_spaces

            res.append(oneline)        
            start_ind = runner

        return res

Answer 1

1. There's no docstring. What does this code do? How do I call it? What does it return?

2. A class represents a group of persistent objects with common behaviour. But there are no persistent objects here, so there is no need for a class. This is also apparent from the fact that the fullJustify method does not refer to self. So don't write a class, just write a function.

3. Python strings have a join method for concatenation. So this code:

   oneline = ""
   for ind in range(start_ind, num_of_words-1):
       oneline = oneline + words[ind] + " "
   oneline = oneline + words[num_of_words-1]
   

   can be simplified to:

   oneline = ' '.join(words[start_ind:])
   

4. Python strings have an ljust method for left-justification within a fixed-width field. So this code:

   pad_spaces = maxWidth - len(oneline)
   oneline = oneline + " "*pad_spaces
   

   can be simplified to:

   oneline = oneline.ljust(maxWidth)
   

5. Python has a built-in function divmod that simultaneously computes the quotient and remainder. So this code:

   basic_pad_spaces = extra_spaces // (word_num - 1)
   addition_pad_spaces = extra_spaces % (word_num - 1)
   

   can be simplied to:

   basic_pad_spaces, addition_pad_spaces = divmod(extra_spaces, word_num - 1)
   

6. Left justification has to be done in two cases: a single word on a line, and the last line. It would therefore make sense to extract this common code into a function:

   def left_justify(words, width):
       """Given an iterable of words, return a string consisting of the words
       left-justified in a line of the given width.
   
       >>> left_justify(["hello", "world"], 16)
       'hello world     '
   
       """
       return ' '.join(words).ljust(width)
   

   Even though this is a simple one-line implementation, giving it a name improves the readability of the code where it is called. Note also the example in the docstring: this can be run and checked using the doctest module.

7. When you are writing code that takes an input sequence (here, some words) and produces an output sequence (here, the justified lines), then it's a good idea in Python to write the code so that it iterates over the input (using for), and generates the output (using yield).

   With this approach: there's no need to keep the whole input and output sequences in memory at once (you operate on one or a few items at a time); there's no need to remember indexes into the input sequence (you just process each item as you get it); and there's no need to accumulate and return the output sequence (you just yield each item as you compute it).

   In this case:

   def justify(words, width):
       """Divide words (an iterable of strings) into lines of the given
       width, and generate them. The lines are fully justified, except
       for the last line, and lines with a single word, which are
       left-justified.
   
       >>> words = "This is an example of text justification.".split()
       >>> list(justify(words, 16))
       ['This    is    an', 'example  of text', 'justification.  ']
   
       """
       line = []             # List of words in current line.
       col = 0               # Starting column of next word added to line.
       for word in words:
           if line and col + len(word) > width:
               if len(line) == 1:
                   yield left_justify(line, width)
               else:
                   # After n + 1 spaces are placed between each pair of
                   # words, there are r spaces left over; these result in
                   # wider spaces at the left.
                   n, r = divmod(width - col + 1, len(line) - 1)
                   narrow = ' ' * (n + 1)
                   if r == 0:
                       yield narrow.join(line)
                   else:
                       wide = ' ' * (n + 2)
                       yield wide.join(line[:r] + [narrow.join(line[r:])])
               line, col = [], 0
           line.append(word)
           col += len(word) + 1
       if line:
           yield left_justify(line, width)
   

Answer 2

Why on Earth are you storing fullJustify as a function in the class Solution? In fact, the class solution serves no purpose whatsoever. It can be removed.

Secondly, function names and variable names should be in the style snake_case, not camelCase. Classes should be in PascalCase.

The three comments above the function Solution.fullJustify, should be stored in a docstring. Here's how you could convert those comments.

def full_justify(words, max_width):
    """
    words     - string[]
    max_width - integer
    returns  - string[]
    """
    ...

This line can be shortened from len_of_line = len_of_line + len(words[runner]) to len_of_line += len(words[runner]). There are other places you could do this. This syntax also supports other operators, like *, or /.

Finally, I find it to be clearer to declare variables on separate lines. For example, the line len_of_line, word_num_line = 0, 0 would become two separate lines, len_of_line = 0, and word_num_line = 0.