{x}
blog image

Text Justification

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

Solution Explanation: Text Justification

This problem requires formatting a list of words into lines with a fixed maxWidth, ensuring full justification (evenly distributed spaces) except for the last line, which is left-justified.

Approach:

The solution uses a greedy approach. It iterates through the words, adding them to a current line until the line's length exceeds maxWidth. When a line is full or the end of the word list is reached, it handles justification and adds the line to the result.

  1. Line Construction: The algorithm iterates through the words. For each word, it checks if adding the word (plus necessary spaces) to the current line exceeds maxWidth. If not, the word is added.

  2. Justification:

    • Last Line or Single Word: If it's the last line or only one word is on the line, the line is left-justified. Spaces are appended to the end to reach maxWidth.
    • Full Justification: If the line has multiple words and isn't the last line, spaces are distributed as evenly as possible. The algorithm calculates the total number of spaces needed (spaceWidth), the base number of spaces between each word (w), and the remainder of spaces (m). The remainder spaces are added to the leftmost spaces between words.

  3. Result: The justified line is added to the ans list.

Time Complexity: O(L), where L is the sum of the lengths of all words. The algorithm iterates through each word once to build lines and justify them. String manipulation operations (joining, repeating spaces) take time proportional to the lengths of strings involved, ultimately related to L.

Space Complexity: O(L). The space used is dominated by the ans list which stores the resultant lines. In the worst case, each word could be on its own line resulting in a list of size L (in terms of characters).

Code Explanation (Python):

class Solution:
    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
        ans = []
        i, n = 0, len(words)  # Initialize index and length
        while i < n:
            t = []  # current line
            cnt = len(words[i])  # length of current line
            t.append(words[i])
            i += 1  # move to the next word
            # build the line until it exceeds maxWidth
            while i < n and cnt + 1 + len(words[i]) <= maxWidth:
                cnt += 1 + len(words[i])
                t.append(words[i])
                i += 1
 
            # handle last line or single-word line
            if i == n or len(t) == 1:
                left = ' '.join(t)  # join words with spaces
                right = ' ' * (maxWidth - len(left))  # add trailing spaces
                ans.append(left + right)  # add line to result
                continue
 
            # handle full justification
            space_width = maxWidth - (cnt - len(t) + 1) #total space
            w, m = divmod(space_width, len(t) - 1)  # spaces between words
            row = []
            # add spaces between words
            for j, s in enumerate(t[:-1]):
                row.append(s)
                row.append(' ' * (w + (1 if j < m else 0)))  #add extra space if needed
            row.append(t[-1]) #add the last word
            ans.append(''.join(row))  # add to the result
        return ans

The other language versions follow a very similar logic, adapting syntax and standard library functions accordingly. The core algorithm remains consistent.