Text Justification — LeetCode 68 Python Solution
HardArrayStringSimulation
- Problem
- #68
- Pattern
- Hash Map
- Reading time
- 5 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
- Output
- [
Python solution
Python
class Solution:
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
ans = []
i, n = 0, len(words)
while i < n:
t = []
cnt = len(words[i])
t.append(words[i])
i += 1
while i < n and cnt + 1 + len(words[i]) <= maxWidth:
cnt += 1 + len(words[i])
t.append(words[i])
i += 1
if i == n or len(t) == 1:
left = ' '.join(t)
right = ' ' * (maxWidth - len(left))
ans.append(left + right)
continue
space_width = maxWidth - (cnt - len(t) + 1)
w, m = divmod(space_width, len(t) - 1)
row = []
for j, s in enumerate(t[:-1]):
row.append(s)
row.append(' ' * (w + (1 if j < m else 0)))
row.append(t[-1])
ans.append(''.join(row))
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(L) |
| Space | O(L) auxiliary |
Pattern: Hash Map
Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 68. Text Justification is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.
Related problems
On a study list
This problem is on Top Interview 150.
Frequently asked questions
- How hard is LeetCode 68. Text Justification?
- LeetCode 68. Text Justification is rated Hard on LeetCode.
- What is the time complexity of LeetCode 68. Text Justification?
- The Python solution on this page runs in O(L).
- What is the space complexity of LeetCode 68. Text Justification?
- The Python solution on this page uses O(L) auxiliary space.
- What topics does LeetCode 68. Text Justification cover?
- LeetCode 68. Text Justification is tagged Array, String and Simulation on LeetCode.