LeetCode 68. Text Justification

November 1, 2024

This took a while to solve. I completed it over two days, then I had the help of ChatGPT to analyze the complexity. I reviewed other answers and I didn't find simpler methods.

Solution

Copy
1class Solution:
2    def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
3        width = 0
4        rows = []
5        row = []
6        for word in words:
7            line = ' '.join(row + [word])
8            if len(line) > maxWidth:
9                charCount = len(''.join(row))
10                spaceRemaining = maxWidth - charCount
11                if len(row) > 1:
12                    spaces = [spaceRemaining // (len(row) - 1) for _ in range(len(row) - 1)]
13                    for i in range(spaceRemaining % (len(row) - 1)):
14                        spaces[i] += 1
15                else:
16                    spaces = [spaceRemaining]
17                print(spaces, row)
18                line = ''
19                for i in range(len(row)):
20                    line += row[i]
21                    if i < len(spaces):
22                        line += ' ' * spaces[i]
23                rows.append(line)
24                row = []
25            row.append(word)
26
27        charCount = len(' '.join(row))
28        spaceRemaining = maxWidth - charCount
29        line = ' '.join(row)
30        line += ' ' * spaceRemaining
31        rows.append(line)
32        return rows

O(n) = n * m where n is the number of words and m is the average row length

LeetCode 28. Find the Index of the First Occurrence in a String

LeetCode 30. Substring with Concatenation of All Words